Math question: How to compute the area of polygons

[Dar Scott]

Ah, this is really an intersection problem.

The idea of seeing if the area of the union of two sets of points 
defined by two polygons decreases is pretty clever.  However, I am not 
smart enough to see how to do that without doing the same work as 
intersection calculation and then much more.  I'm going to keep it in 
mind, because it might be handy some time.

On Wednesday, March 19, 2003, at 08:08 AM, Malte Brill wrote:
>
> Perhaps I should follow the tips that were suggested on this list a few
> month earlier checking the image- and maskdata of the objects and look 
> if
> their values are bigger than a certain threshhold.

If you are using images, that may is the way to go.

If you are using polygons or associate polygon data with an image 
consider this:

I'm guessing that two polygons intersect if (and only if) at least one 
of these are true:
1.  Some edge of one polygon intersects with an edge of the other 
polygon.
2.  An arbitrary point of one polygon is inside the other polygon.

If your polygons are moving when colliding and can't start out 
overlapping, then maybe you can get by without the second test.  That 
is because the only time the second is true and the first is not is 
when one polygon is completely enclosed in the other.  If collisions 
are always detected before that happens then you don't need to test for 
that.

1. Some edge of one intersects with an edge of the other.

When you iterate through all edges, be sure to include the last one, 
that is, the one from the last point to the first point.

Consider an edge as a line segment.  Two line segments intersect if the 
lines that include them intersect and the point of intersection is on a 
segment.  The test for the latter can be simplified to the x component 
of the point being within the two x components of the end points of the 
segment.

The intersection test not only tests for intersection, but also comes 
up with the x component of the point for the second part of the above 
test.  To create this test apply algebra to come up with the formula 
for a line defined by two points.  Then solve the system of equations 
formed by two of those.  Watch out for dividing by zero (or near zero); 
the lines do not intersect in that case.  Test for zero in the code.  
Watch out for vertical lines.

2. The first point of one is inside the other polygon.

This doesn't have to be done for all points, I think, because of test 
#1.

This may have to be done in two parts.  Once for a point of the first 
and again for a point of the second.

I don't know the best test of whether a point is in a polygon.  Here is 
a wild guess.  First, break the polygon into triangles.  (Since the 
polygon can be concave, you can't assume every corner is convex; that 
is, you can't chop triangles off the polygon in any order.)  You may 
want to do this once and save it.  Then see if the point is in any of 
the triangles.

A point is in a triangle when it is a neighbor of each corner of the 
triangle.  (I just made up the term "neighbor".)  A point is a neighbor 
of a point that is a corner of a triangle if it is on the same side of 
the partition of the plane formed by the line including the side 
opposite the point.  A first try for a method:  To determine which side 
a point is on see whether its y component is greater than the value 
obtained when plugging the x component into the y= form of the formula 
for the line, but you may need to handle a vertical line as a special 
case.  With a little thought you may come up with a general test.

This is a little more work than the other because of breaking the 
polygon into triangles, so if you can get by without it, that would be 
good.


If you are using a polygon as a rough model for an image, you might be 
better off using a set of rectangles to represent the object for 
collision detection purposes.  (This is, I admit, a rougher model.)  In 
this case, two objects overlap if any test-rectangle of one overlaps a 
test-rectangle of the other.

The time it takes to make a test goes up with the square of the number 
of sides in a typical polygon.

Dar Scott