omh@nancy (Owen M. Hartnett) (03/23/88)
Does anyone have a good method for determining the area (square pixels) of a
Macintosh polygon? The method I'm going to use would be to copy it to a
blank offscreen bitmap, then scan through the bits looking for an edge, then
count bits until I hit the next edge.
Any better ways (or a fast algorithm to do the above??)
Thanks,
Owen
Owen Hartnett
Brown University Computer Science
omh@cs.brown.edu.CSNET
omh%cs.brown.edu
{ihnp4,allegra}!brunix!omh
"Don't wait up for me tonight because I won't be home for a month."
-W.C. Fieldsgillies@uiucdcsp.cs.uiuc.edu (03/25/88)
Do you really need the area of your polygon in pixels? There is a
very efficient way to determine the area of a polygon numerically.
You take one point and use it to break the polygon into triangles.
There is a linear-algebra formula that gives the area of a triangle
given two vectors. The area is positive if you take the vectors in
clockwise order, and the area is negative if you take them in
counterclockwise order. I think the formula is the magnitude of the
cross product ( | A x B | / 2 = |A||B|sin(theta) / 2), but I'm extremely
rusty at linear algebra.
You just add up all the (positive/negative) areas to get the total area.
You can convince yourself that this works with a pencil and paper --
draw a polygon, pick one point, draw a line from it to every other
point. Now start at that point and go clockwise around the polygon.
For each two vectors to points on the polygon, add the area of the
resulting triangle if the vectors are in clockwise order, or subtract
the area if they're in counter-clockwise order. You should end up
with an area that fits exactly within your polygon.
Don Gillies {ihnp4!uiucdcs!gillies} U of Illinois
{gillies@p.cs.uiuc.edu}
P.S. You take the cross product in 3 dimensions, the x and y
components are always zero, and you divide the z dimension by two to
get the area of the triangle.gillies@uiucdcsp.cs.uiuc.edu (03/26/88)
If you want to count the bits in a bitmap, it's going to be slow, but
you can be clever and speed things up quite a bit
- 1. Loop through all the computer words in the bitmap. Use the
largest word-size possible (32-bits). Skip over words that are zero.
- 2. For non-zero N-bit (32-bit) words, you can count the bits in
parallel using LogN (5) steps. For details, see "Combinatorial
Algorithms", chapter 1, but Reingold, Nievergelt, Deo. Briefly, in C,
it might look like:
bitsum(X)
long unsigned X;
{ long unsigned Y, Z;
#define Mask1 025252525252 /* every other bit */
#define NotMask1 ~Mask1
#define Mask2 031463146314 /* 2 bits on, 2 bits off */
#define NotMask2 ~Mask2
...
Y = (X & Mask1) >> 1; /* step 1 */
Z = (X & NotMask1);
X = Y + Z;
Y = (X & Mask2) >> 2; /* step 2 */
Z = (X & NotMask2);
X = Y + Z;
/* step 3: 4 bits on, 4 bits off, shift by 4 */
/* step 4: 8 bits on, 8 bits off, shift by 8 */
/* step 5: 16 bits on, 16 bits off, shift by 16 -- Done */
/* for efficiency, don't use vars Y & Z, compress this
subroutine into 5 assignments to the X variable, e.g.
X = (X & NotMask1) + ((X & Mask1) >> 1);
*/
}
Essentially, you are adding up all the bits in parallel. The first
step does 16 single-bit adds in parallel. The second step does 8
double-bit adds in parallel. The third step does 4 quad-bit adds in
parallel, and so on.
Don Gillies {ihnp4!uiucdcs!gillies} U of Illinois
{gillies@p.cs.uiuc.edu}jv0l+@andrew.cmu.edu (Justin Chris Vallon) (04/05/88)
>[stuff about finding the area of a polygon]
Since you know the verticies of the polygon (as far as I gather from your
post), apply a very simple algorithm:
Area = 0
ForEach edge (E) in polygon with endpoints P1, P2:
Area = Area + (P1.h + P2.h)*(P1.v - P2.v)/2
Note that you'll probably have to use long-ints, or bigger to prevent
overflows. This is about as simple as it could get.
-Justinb39756@tansei.cc.u-tokyo.JUNET (Martin J. Duerst) (04/26/88)
Here is another method to count bits. Hope this helps: Build up a table with 256 entries, one for each possible value of a byte, containing the number of '1' bits for the corresponding byte, like the following: 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, etc. (These are the values of the first few entries.) This table has to be built up only once for the whole program. For counting the bits, take each byte of your picture and look up the corresponding value in the table. Adding up all the values for all the bytes of your picture will give you the right result. Smaller or larger tables (e.g. size 2**16) are also possible, but may be use too much space or too much time to build up. 256 is a very convenient size. This should be quite fast if nicely implemented, but I didn't try it myself. Martin J. Duerst UUCP: See header. Dept. of Information Science BITNET: TU$KUNII@JPNSUT00 Faculty of Science (The '$' in the userid makes University of Tokyo this unaccessible from many 7-3-1 Hongo, Bunkyo-ku sites.) 113 Tokyo, Japan
newbery@rata.vuw.ac.nz (Michael Newbery) (04/29/88)
I've used the number-of-bits-in-a-byte technique and it works just fine, takes just a few seconds to count the bits in a MacPaint document (background: someone wanted the area of a complex object, so we Thunderscan a photo and count the bits.)