Math question: How to compute the area of polygons

[Geoff Canyon]

On Wednesday, March 19, 2003, at 09:40 AM, Dar Scott wrote:

> Ah, I just mailed off the same idea.  There is a hole.  That is the 
> case of one being completely inside the other.  I covered that in my 
> mailing, but it may not be needed.
>

Good catch. I just though of an alternative:

There is a fairly simple and quick test to see if a point is inside a 
polygon of any shape: from the point, draw an imaginary horizontal line 
either to the right or left, to infinity. Get the formula for that 
line, and figure out how many line segments of the polygon it 
intersects. If it intersects an odd number, the point is inside the 
polygon. If it intersects an even number, the point is outside the 
polygon. It's a fairly fast check because the formula for a horizontal 
line is easy to work with/find intersections with. You have to watch 
out if the point has the same y component as any of the endpoints of 
the polygon -- that reverses the answer, I believe.

So, using that test, you test points from each of the polygons to see 
if they are inside of each other. You have to test points from both 
polygons, since the pointy bit of either could be sticking into the 
other, without any points of the other being inside the first.

The first point you find that is inside the other, you have a hit and 
you exit. The tricky bit is figuring out which points to test -- don't 
test them all, it's too much work. But that's optimization, left as an 
exercise for the reader ;-)

regards,

Geoff Canyon
gcanyon at inspiredlogic.com