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
_______________________________________________ use-revolution mailing list [EMAIL PROTECTED] http://lists.runrev.com/mailman/listinfo/use-revolution
