Math question: How to compute the area of polygons

[Dar Scott]

On Wednesday, March 19, 2003, at 10:47 AM, Jim Hurley wrote:

> But you have to do this for each line segment pair. If there are n 
> line segments in one sprite and m in the other, there will be n*m 
> potential intersections. Heavy!!!
>
> If it were me, I would just fake it by calling it a collision if the 
> distances between their centers (locs) are less than a specified 
> number. But I am a person of loose morals.

And I tend to legalistic.

There may be a way to mix styles.  If we limit our attention to the 
intersection of the bounding rectangles of the two polygons, then we 
can eliminate those line segments that do not intersect or are 
otherwise not "near" the intersection rectangle.  In the worse case 
this is more work, but on the average it should be less "heavy".  Use 
your "loose morals" to come up with "near".


While daydreaming I got to wondering of an approach to both the "loose 
morals" and the "legalistic" approach.  In this approach we consider 
the intersection rectangle of the bounding rectangles.  Each control, 
be it image or graphic or whatever, that can be considered in 
collisions can be asked a question.  Controls you make might answer 
simply and quickly.  Controls I make might answer exactly and slowly.  
The the collision function for two controls looks at the intersection 
rectangle and based on that asks questions of the controls to decide 
whether there is a collision.

Because this is somewhat object-oriented, it is possible to customize 
the function or handler that responds to questions.  If you have only a 
small set of classes of controls involved, then writing a brute-force 
script for each one may be the simplest and fastest way to go.  Some 
fast moving controls might look into the future slightly to answer the 
question.

I realize the abstract & obscure description is hard to follow.  Here 
are a couple more specific ways to do this.

One way to ask a question is to send a message and look for the result 
in a few global variables.

In the examples below, a transparency value or a transparency interval 
can be returned.  However, for simplicity I'm going to use a boolean 
value or a boolean interval (a pair in which "huh?" is represented as 
"true, false", true is represented as "true, true" and false is 
represented as "false, false").  In the discussion true is considered 
greater than false.

First, I'll describe a simple point test method and then a region test 
method (with an interval answer).

For the point test method, the question asked of each control is "Is 
this point inside your shape?"  Then to detect collision, I simply test 
some interesting subset of points in the intersecting rectangle looking 
for one in which the answer is true for both.

Candidates for the subset might be all, the corners, the edges, a grid, 
or some random combination of points from those as sculptured by some 
designer with "loose morals" who knows the application.

Note that on your control, you can use a circle model and, on my 
control, I can use a more complicated model.

Warning.  The next method uses recursion.

For the region test method, a more complicated question is asked.  
"Given a rectangle, if the above question is asked for every point in 
the rectangle, what would be the max and min answers?"  If the shape 
does not intersect with the rectangle, an answer of "false, false" is 
given.  If the rectangle is completely within the shape, then an answer 
of "true, true" is returned.  Otherwise, "true, false" is returned.  
(The handler may "lie" and return "true, false" as long as it supplies 
a definitive answer for a smaller rectangle, should this tend to give 
better performance.)  The shape may not answer "true, false" for a 
trivially small rectangle (whatever that is), that is, a most small 
rectangle.

The collision detector will start with the intersection rectangle and 
ask each shape the question and may recursively break up the rectangle 
and ask more questions as needed.  If either shape returns "false, 
false" for a rectangle, there is no collision.  If both shapes return 
"true, true" then there is is a collision.  Otherwise the rectangle is 
broken into two rectangles about equal shape and most squarish.  If 
either of those show a collision then the original rectangle shows a 
collision.

This can be faster if controls are good at returning "true, true" or 
"false, false", thus allowing the search to be narrowed down enough to 
more than offset the extra cost of computing the region result.  I 
think that will be normally the case, but if overlapping rectangles are 
usually small then a brute force point test may be faster.

(I find it interesting that I considered a similar method recently when 
kibitzing on Bible search methods.  There must be some general 
approach.)

Dar Scott