[net.micro.mac] Calculating Region Areas

cohn@ucbvax.ARPA (Ted Cohn) (04/08/85)

A simple process-by-illimination technique can be used to find the area of a
given region (i.e., the number of pixels the region contains).  I remember
someone posting their interpretation of the region structure a few months ago,
but I lost it.  Since I don't know the internal structure of a region, the
QuickDraw routine PTINRGN can be use repeatedly.  Of course, we do know that:

TYPE Region = RECORD
		rgnSize:  INTEGER;
		rgnBBox:  Rect;
		{Optional region definition data}
	      END;

The region is, at most, as big as the enclosing rectangle, rgnBBox.  Therefore,
the area must be the sum of those pixels that fall within the region where
PtInRgn(point,region) is true.  Or, conversely, the area is also equal to the
differnce of the area of rgnBBox and the sum of pixels not in the region where
PtInRgn(point,region) is false.  A simple Pascal function is as follows: 

Function AreaRgn(theRgn: RgnHandle): LongInt;
var h, v, x1, x2, y1, y2: INTEGER;
    thePoint: point;
begin
    x1:=theRgn.rgnBBox.left;
    x2:=theRgn.rgnBBox.right;
    y1:=theRgn.rgnBBox.top;
    y2:=theRgn.rgnBBox.bottom;
    AreaRgn:=(x2-x1)*(y2-y1);		{Find maximum area}
    if theRgn.rgnSize > 10 then		{If more to region, iterate}
	for h:=x1 to x2-1 do		{One less than x2 so not to overcount}
	    for v:=y1 to y2-1 do	{One less than y2 so not to overcount}
	    begin
		SetPt(thePoint, h, v);	{A Pascal frustration}
		if not PtInRgn(thePoint,theRgn) then AreaRgn:=AreaRgn-1;
	    end;
end;

If anyone finds a slicker way of finding region areas, I would love to hear
about it!  Perhaps knowing the internal structure (already decyphered?) might
lend a hand.  Of course, what applications might this function have?
Finding approximate areas of regions on maps in MacPaint maybe?  Who knows.

- Ted Cohn
cohn@ucbvax.BERKELEY.ARPA
"I'd rather be driving a Macintosh"

lsr@apple.UUCP (Larry Rosenstein) (04/09/85)

A faster way to calculate the area of a region would be to create an
off-screen bitmap, do a FillRgn, and counting the 1 bits in the bitmap.
(Of course, you can optimize by checking for rectangular regions first.)

This requires only 1 regions operation, and you do not have to know the
region structure.  Counting the bits should be very fast, and could even be
done in assembler.  (My first thought would be to build a table that maps
the value of a byte into the number of 1 bits it contains, and iterate
through the bitmap a byte at a time.)

The only problem, is that you need to have enough memory for the off-screen
bitmap.


-- 
Larry Rosenstein
Apple Computer

UUCP:  {nsc, dual, voder, ios}!apple!lsr
CSNET: lsr@Apple.CSNET