Using Regions in Medicine with C

By Stephen Dubin, V.M.D., Ph.D., Thomas W. Moore, Ph.D., and, Sheel Kishore, M.S., Drexel University

Fun with Regions: Part I, High Level Language Implementation

As one looks through a tattered and tear-stained copy of Inside Macintosh, there is little that would be considered colorful or dramatic language. The following statement, from the section on Quickdraw, stands out: “Quickdraw has the unique and amazing ability to gather an arbitrary set of spatially coherent points into a structure called a region, and perform complex yet rapid manipulations and calculations on such structures. This remarkable feature not only will make your standard programs simpler and faster, but will let you perform operations that would otherwise be nearly impossible; ...”

One of the authors read this at the very time that he wanted to do something nearly impossible. The job at hand was a medical instructional program, “Burnsheet”, in which the outline of a thermal injury is drawn on a standard silhouette of the body (fig 1.). Since many formulas for treating burn patients depend on knowing the area affected, it was desirable to calculate the area of the burn(s) as well. Thus the specific programming tasks were to be able to draw arbitrarily shaped regions on the screen and to find the area of these areas. This first article will show an approach to these tasks using high-level (C and Pascal) programming. The complete code for a C language program is at the end of the article; and the important routines, as implemented in Pascal, are interpolated into the text. In many cases programming elegance has been sacrificed for the sake of clarity; especially when an elegant approach could not be found. Part II will present an evolutionary approach to the assembly language optimization for speed in the computation of arbitrary areas on the Macintosh.

In addition to Inside Macintosh, some germinal information on region drawing is found in “Quickdraw Does Regions” (Derossi, C., MacTutor 1, February 1985 pp 9-17). He outlines the basic steps as follows: (a) Initialize a variable ( a regionhandle) with a call to NewRegn. (b) Call OpenRgn to start a new region. (c) Do whatever drawing you want. (d) Call CloseRgn to stop the region definition. In a more recent article (Gordon, B.: Polygons and Regions as Quickdraw Objects. MacTutor May 1987, pp 41-53 ), further insight is given into the way regions are encoded - especially the mysterious optional region drawing information which is present when a region is not rectangular.

The matter of finding the area of irregular regions is quite a common task in geography, chemistry (chromatograph spots, for example), and many aspects of biology. Methods for accomplishing the task range from analytic solutions where the boundaries are defined by well-behaved mathematical functions to such brutal kluges as weighing paper on which the region has been traced. An elegant general approach for finding the area of a large class of irregularly shaped regions divides the region into triangles and trapezoids (Stolk, R., and Ettershank, G.: Calculating the Area of an Irregular Shape. Byte, February 1987, pp 135-136.) This method requires, however, that the vertices of the perimeter be described explicitly as cartesian coordinates - not the Macintosh definition. It will not work for regions that are disjoint or have holes in them.

Region Drawing Routines: Although several published programs have shown how to create regions on the screen by passing explicit parameters to drawing commands; such as

FrameRect(myRect,10,20,30,40), etc., 

what I wanted was to draw an arbitrarily shaped region on the fly under mouse control - something like the lassoo in many Mac graphics programs. My answer to this need is the DoRegion procedure. It is well to initialize the global regionhandle TotalRgn early in the program. In the C program shown this is done just before the main event loop in order to avoid a bomb if the area computation is requested before the region is actually drawn.

A Pascal implementation of the procedure is as follows:

{1}
var
 TotalRegion   :   RgnHandle;

procedure DoRegion;
var
    p1  :   Point;
    p2  :   Point;
    OldTick :  Longint;    
begin
  TotalRegion := NewRgn;
  OldTick := TickCount;
  Repeat
    GetMouse(p1);
    MoveTo(p1.h,p1.v);
    p2 := p1;  
  Until Button = True; 
  OpenRgn;
  ShowPen;
  PenMode(patXor); 
  Repeat
    GetMouse(p2);
    Repeat Until (OldTick <> TickCount);
    LineTo(p2.h,p2.v);
  Until Button <> True; 
  Repeat Until (OldTick <> TickCount);
  LineTo(p1.h,p1.v);
  PenNormal;
  HidePen;
  CloseRgn(TotalRegion);
  InvertRgn(TotalRegion);
end;

The mouse position is tracked until the button is pressed. While the button is down, a sequence of lines is drawn following the movement of the mouse. In order to make the drawing less jumpy, it is synchronized with the vertical retrace period by waiting until the “tickcount” changes before updating the drawing process (Knaster, S.: “How to Write Macintosh Software”, Hayden, Hasbrouck Heights, NJ, 1986, pp 334-336). The calls to ShowPen and HidePen are necessary to balance opposing calls made by OpenRgn and CloseRgn.

An analogous procedure for drawing a rectangle under mouse control is shown below:

{2}
var
 TotalRegion   :   RgnHandle;

procedure DoBox; 
var
    p1  :   Point;
    p2  :   Point;
    p3  :   Point;
    OldTick :  Longint;
    MyRect  :  Rect;      
begin
    TotalRegion := NewRgn;
    OldTick := TickCount;
    PenPat(gray);
    PenMode(patXor);
    Repeat
      GetMouse(p1);
      p2 := p1;  
    Until Button = True;
    OpenRgn;
    ShowPen;
    PenMode(patXor);
    Repeat
      Pt2Rect(p1,p2,MyRect);
      Repeat Until (OldTick <> TickCount);
      FrameRect(MyRect);
        Repeat
            GetMouse(p3);
        Until  EqualPt(p2,p3) <> True;
   
   Repeat Until (OldTick <> TickCount);
   FrameRect(MyRect);
   p2 := p3;
   Until Button <> True;
   Pennormal;
   HidePen;
   PenPat(black);
   FrameRect(MyRect);
   CloseRgn(TotalRegion);
   InvertRgn(TotalRegion);
end;

After the mouse button is pushed, a “preview” rectangle is drawn in gray as the mouse position is changed. When the button is released, the rectangle is “enforced” as the final choice. Although these procedures invert the pixels in the region finally chosen, various types of painting or filling could also be done and the last FrameRect in DoBox could be changed to FrameOval, etc.

Area Computation: The region record contains the coordinates of the smallest rectangle which will enclose the region, the rgnBBox. As a first approach to determining the region area, one might “take a poll” of every pixel within this box to see whether it is actually in the region. The toolbox function PtInRgn, when passed a point and a handle to a region, returns the Boolean value true if the point actually resides within the region. The number of true points enumerated in this way should be proportional to the area of the region with a degree of precision at least as good as the ability to draw on the screen with the mouse.

{3}
function CountPix(theRegion : RgnHandle): LongInt
var
 pt     : Point;
 rgn    :   Region;
 temp   :   LongInt; 
  
begin
 temp :=  0;
 rgn  :=  theRegion^^;
 for pt.h := rgn.rgnBBox.left to rgn.rgnBBox.right do 
 begin
 for pt.v := rgn.rgnBBox.top to rgn.rgnBBox.bottom do
 if PtInRgn( pt, TheRegion) then temp := temp + 1;  
 end;
 CountPix := temp;
end;

The C and Pascal Countpix routines work nicely for relatively small regions. For those drawn in the Burnsheet program, processing time ranged from three to thirty ticks (6oths. of a second). It is possible, however, to draw really large and bizarre regions with many holes that can take ten minutes to compute. Although finding the area of such regions by conventional means “would otherwise be nearly impossible,” this is hardly a satisfactory performance; and clearly some form of optimization is indicated. An important step towards fashioning and debugging a faster routine for estimating the area of an arbitrary region is a method for visualizing the region information as it exists in RAM. Although this can be done using a debugger, it is more convenient to have this as part of our region program. The C version of the “data” function reflects that language’s general laissez faire attitude concerning mixing of pointer types in the blockmove step. Because of the ease with which the type of numerical representation (hex or decimal) can be specified within the printf routine, the C version first prints the hex version - as it would be seen with a debugger. After a mouse click, the decimal version is printed to the screen. Pascal seems to be more finicky about mixing different pointer types, so explicit type conversions are done. The Pascal version displays only the decimal representation of the data. In both versions only the first 400 words of data are shown since this fits conveniently on the screen. Displaying the hex numbers in Pascal and adding scrollers to display more data are - in the words of my old calculus book - left as an exercise for the reader.

{4}
{ This routine prints the first 400 words of a region record to the screen. 
It assumes that a regionhandle called totalRegion has been declared and 
allocated }

procedure Data;  
var
    rgn         :   Region;
    rgnpntr     :   Ptr;
    size        :   Integer;
    halfsize    :   Integer;
    thebuf      :   BUF;
    bfpntr      :   Ptr;
    myString    :   Str255;
    i           :   Integer;
    x           :   Integer;
    y           :   Integer;
 
 begin
    Wipe;
    TextSize(9);
    TextFont(Monaco);
    rgn  :=  totalRegion^^;
    rgnpntr := ptr(totalRegion^); 
    size := rgn.rgnSize;
    if size > 800 then size:= 800;
    bfpntr := ptr(@thebuf);
    BlockMove(rgnpntr,bfpntr,size);
    MoveTo(10,10);
    DrawString(‘Here are the first 400 words of the region data. (FLAG 
= 32767)’);
    x := 10;
    y := 20;
    for i  := 1  to  (size div 2) do 
        begin
        MoveTo(x,y);
        NumToString(theBuf[i],myString);
        if theBuf[i] < 32766 then 
            begin
            if theBuf[i] <10  then DrawString(‘ ‘);
            if theBuf[i] <100 then DrawString(‘ ‘);
            if theBuf[i] <1000 then DrawString(‘ ‘);
            if theBuf[i] <10000 then DrawString(‘ ‘);
            DrawString(MyString);
            end;
        if theBuf[i] > 32766 then DrawString(‘ FLAG’);
        x := x + 30;
        if (i mod 16) = 0 then
            begin
            x := 10;
            y := y+10;
            end; 
        end; 
end;

Figure 2 shows a “FatBits” view of a circle along with the function used to draw it and acquire a handle to the region it encloses. Figure 3 shows the data for this region as displayed by our data routine. Using this information you can trace the way the region is encoded as as outlined in Bob Gordon’s article (vide supra ). The first word (196) is the number of bytes of data in the record. The next four words are the coordinates of the region bounding box in “upper, left, bottom, right” form. The rest of the data consists of sequences as follows: Y,X1, X2, ...Xn, FLAG. The flag word is 32767 (7FFF hex). At the very end of the record, the flag word appears twice. In each sequence the first integer word is a Y coordinate and the others up to the flag are X coordinates. One may visualize the process of outlining the region by thinking of moving a “pen” to the Y coordinate and toggling it on and off with each succeeding X value. For the circle shown (starting with the fifth word of data), the first Y position is 175 and the first X coordinate is 179. Turn the pen on at this point and draw rightward to the second X coordinate (186). Turn off the pen. Similarly expanding the next sequence: move to ( Y = 176, X = 177); pendown; moveto (X = 179); penup; moveto(x = 186) - Y remains the same; pendown; moveto(x = 188); penup. Note that treating the data in this manner will draw all of the horizontal lines needed to frame the region.

This representation of data is particularly efficient for dealing with regions with “square corners” - the sort that occur when windows overlap, etc. Even for more complex objects, the amount of data to be stored is much less required by more intuitive methods such as simply listing all of the points in the region or the vertices of its boundaries.

Figure 4. shows a screendump of a really horrible region along with the times needed to estimate its area using the high level code presented here and with various levels of optimization. Using the high level routine, it required about seven and a half minutes to compute its area. By way of comparison, the small regions shown in the “Burnsheet” illustration (Figure 1.) took less than a second using the same code. For complex regions such as this, the assembly language optimization improves the speed of computation by a very welcome factor of more than 1000.

Stephen Dubin, V.M.D., Ph.D., Thomas W. Moore, Ph.D., and Sheel Kishore, M.S. may be reached at the Biomedical Engineering and Science Institute, Drexel University, 32nd. & Chestnut Sts, Philadelphia PA 19104. Phone: (215)-895-2219. CIS: 76074,55 ; Genie: S.DUBINp; Delphi: ESROG.

{5}
/* *****Region.c **************
written by Stephen Dubin and Sheel Kishore  copyrignt 1987 for MacTutor
Latest revision 8/9/87
Prepared with Megamax C System V3.0d. Users of other C systems should 
check for such things as size and manner of passing variables particularly 
point variables. Also check include files. */

#include  <qd.h>  
#include  <win.h>
#include  <dialog.h>
#include  <menu.h>
#include  <event.h>
#include  <qdvars.h>
#include<stdio.h>

#define lastmenu 1 /* number of menus*/
#define optionmenu 1
#define NULL 0L 
/* globals used by shell */

menuhandle mymenus[lastmenu+1];
rect screenrect, prect;
boolean doneflag, temp;
eventrecord myevent;
int code, refnum;
windowrecord wrecord;
windowptr mywindow, whichwindow;
int themenu, theitem;

/* globals used by region */
rgnhandle totalrgn;
extern long tickcount();
long  numpix,numtix; 

area()
{
long firstick,lastick;
char  firststring[255], secondstring[255], printstring[255];
 numpix = 0;
 firstick = tickcount();
 countpix(totalrgn);
 numtix = tickcount() - firstick;
 moveto(10,20); drawstring(“Using all C code”);
 strcpy(firststring,””);strcpy(printstring,””);
 numtostring(numpix,firststring);
 strcat(printstring,”Number of Pixels = “);
 strcat(printstring, firststring);strcpy(firststring,””);      
 moveto(10,30); drawstring(printstring); strcpy(printstring,””);
 numtostring(numtix,firststring);
 strcat(printstring,”Number of Ticks = “);
 strcat(printstring, firststring); strcpy(firststring,””);
 moveto(10,40); drawstring(printstring); strcpy(printstring,””);
 
}

countpix(theregion)
rgnhandle theregion;
{
point pt;
region rgn;
 rgn = **theregion;
 for(pt.a.h=rgn.rgnbbox.a.left; pt.a.h <= rgn.rgnbbox.a.right; pt.a.h++)
 for(pt.a.v=rgn.rgnbbox.a.top; pt.a.v <= rgn.rgnbbox.a.bottom; pt.a.v++)
 if (ptinrgn(&pt, theregion))
 numpix++;
}

data()
{
region  rgn;
intsize,i;
intmyarray[400];
                                                               wipe();
 rgn = **totalrgn;
 size = rgn.rgnsize;
 size = ( (size > 800) ? 800: size); 
 blockmove(*totalrgn, &myarray, (long)size);
 moveto(10,10);
 printf(“Here is the first 400 words of region data in hexadecimal notation:\n”);
 for(i=0; i<(size/2); ++i) {
 printf(“ %04x”,myarray[i]);
 if(!((i+1)%16)) printf(“\n”);
 }
 printf(“ Press the mouse button to continue.”);   
 fflush(stdout);
 while (!button());
 wipe();
 moveto(10,10);
 printf(“Here is the first 400 words of region data in decimal notation:\n”);
 for(i=0; i<(size/2); ++i) {
 if(myarray[i]>32766) printf(“ FLAG”);
 else printf(“ %04d”,myarray[i]);
 if(!((i+1)%16)) printf(“\n”);
 }
 fflush(stdout);
}

doregion()/* draws freehand region */
{
point   p1,p2;
long  oldtick;
 wipe();
 totalrgn = newrgn();
 while(!button()){
 getmouse(&p1);
 moveto(p1.a.h,p1.a.v);
 p2=p1;
 }
 openrgn();
 showpen();
 penmode(patxor);
 while(button()){
 getmouse(&p2);
 while(oldtick == tickcount());  
 lineto(p2.a.h,p2.a.v);
 }
 while(oldtick == tickcount());  /* to avoid flickering */
 lineto(p1.a.h,p1.a.v);
 pensize(1,1);
 pennormal();
 hidepen();
 closergn(totalrgn);
 invertrgn(totalrgn);
}

dobox() /* draws rectangular region  */
{
point p1,p2,p3;
boolean equalpt();
long  oldtick;
rect  myrect;
 wipe();
 oldtick = tickcount();
 totalrgn = newrgn();
 penpat(gray);
 penmode(patxor);
 while(!button()){
 getmouse(&p1);
 p2=p1;
 }
 openrgn();
 showpen();
 penmode(patxor);
 while(button()){
 pt2rect(&p1,&p2,&myrect);
 while(oldtick == tickcount());/* to avoid flickering */
 framerect(&myrect);
 while (equalpt(&p2,&p3)&& button()) getmouse(&p3);
 while(oldtick == tickcount());
 framerect(&myrect);
 p2=p3;
 } 
 pensize(1,1);
 pennormal();
 hidepen();
 penpat(black);
 penmode(patcopy);
 framerect(&myrect);
 closergn(totalrgn);
 invertrgn(totalrgn);
 pennormal();
}

wipe()
{
rect  r;
 setrect(&r,0,0,510,300);
 eraserect(&r);
 pennormal();
}

setupmenus()
{
int i;
    initmenus();
    mymenus[1] = newmenu(optionmenu,”Options”);
    appendmenu(mymenus[1], “Draw Freehand;Draw Box;Compute Area;Region 
Data;Quit”);
    for (i=1; i<=lastmenu; i++) insertmenu(mymenus[i], 0);
    drawmenubar();
}

docommand(themenu, theitem)
int themenu, theitem;
{
int i;
    switch (themenu) {
 case optionmenu:
 switch(theitem){
 case 1: doregion(); break;
 case 2: dobox(); break;
 case 3: area(); break;
 case 4: data(); break;
 case 5: doneflag = 1; break;
 }
 break;
     }
    hilitemenu(0);
}

main()
{
rect windowrect;
    initgraf(&theport);
    initfonts();
    flushevents(everyevent, 0);
    initwindows();
    setupmenus();
    initdialogs(NULL);
    initcursor();
    setrect(&screenrect, 2, 40, 510, 338);
    doneflag = 0;
    mywindow =newwindow(&wrecord,&screenrect,“Region Fun”,1,0,
  (long)-1, 0, (long)0);
    setport(mywindow);
    blockmove(&theport->portrect, &prect, (long)sizeof prect);
    insetrect(&prect, 4, 0);
    textfont(4);
    textsize(9);
    textmode(2);
    totalrgn = newrgn(); /* avoid bomb if compute is first */
    do {
      systemtask();
 temp = getnextevent(everyevent, &myevent);
 switch (myevent.what) {
      case mousedown:
     code = findwindow(&myevent.where, &whichwindow);
     switch (code) {
     case inmenubar:
    docommand(menuselect(&myevent.where)); break;
     case insyswindow:
    systemclick(&myevent, whichwindow); break;
     case incontent:
    if (whichwindow != frontwindow())
     selectwindow(whichwindow);
    else  globaltolocal(&myevent.where);
    break;
         }
 break;
      case updateevt:
     setport(mywindow);
     beginupdate(mywindow);
     wipe();
     endupdate(mywindow);
     break;
     }
    } while (doneflag == 0);
}