Path: utzoo!mnetor!uunet!husc6!bloom-beacon!gatech!ncar!ames!pacbell!att-ih!ihnp4!inuxc!iuvax!pur-ee!uiucdcs!uiucdcsp!gillies
From: gillies@uiucdcsp.cs.uiuc.edu
Newsgroups: comp.sys.mac.programmer
Subject: Re: Polygon question
Message-ID: <104700015@uiucdcsp>
Date: 25 Mar 88 07:36:00 GMT
References: <24153@brunix.UUCP>
Lines: 27
Nf-ID: #R:brunix.UUCP:24153:uiucdcsp:104700015:000:1352
Nf-From: uiucdcsp.cs.uiuc.edu!gillies    Mar 25 01:36:00 1988


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.