Math question: How to compute the area of polygons

[Jim Hurley]

>
>Message: 13
>Date: Wed, 19 Mar 2003 08:05:48 -0800
>Subject: Re: Math question: How to compute the area of polygons
>From: Geoff Canyon <gcanyon at inspiredlogic.com>
>To: use-revolution at lists.runrev.com
>Reply-To: use-revolution at lists.runrev.com
>
>If you're looking for collision detection, I think it would be faster
>to check the line segments of polygon A against the line segments of
>polygon B to see if any of them intersect. If they do, there's a
>collision. There may be a faster way than that, but I think at least
>that it would be faster than computing the areas.

Malte and Geoff,

I like Geoff's suggestion of checking whether any two line segments 
intersect. (The actual values for the areas doesn't tell you much.)

I wrote the function below for my Turtle Graphics but it works here 
as well. It determines the intersection point of any two line 
segments (defined by their end points)

function intersection p1,p2,pp1,pp2
   put item 1 of p1 into x1
   put item 2 of p1 into y1
   put item 1 of p2 into x2
   put item 2 of p2 into y2
   put item 1 of pp1 into xp1
   put item 2 of pp1 into yp1
   put item 1 of pp2 into xp2
   put item 2 of pp2 into yp2
   if x1 = x2 or xp1 = xp2 then
     if x1 = x2 then
       return x1&comma&yp2 + (x1-xp2)*(yp2-yp1)/(xp2-xp1)
     else
       return xp2&comma& y2 + (xp1-x2)*(y2-y1)/(x2-x1)
     end if
   end if
   put yp2 - y2 + x2*(y2-y1)/(x2 - x1) - xp2*(yp2 - yp1)/(xp2 - xp1) 
into numerator
   put ((y2 - y1)/(x2 - x1) -(yp2 - yp1)/(xp2-xp1)) into denominator
--Notice that the denominator blows up if  x1 = x2 or xp1=xp2 and so 
is treated above.
   put numerator / denominator into x
   put y2 + (x-x2) *(y2-y1)/(x2-x1) into y
   return x & comma & y
end intersection

Once you have the intersection point, you need to be sure it does not 
lie beyond the line segments. This could be done as follows. Let p be 
the point  of intersection. Consider one line segment with end points 
a & b. Calculate the following three distances: ap, bp, and ab. The 
point p lies between a and b if ap and bp are both less than ab. (If 
the intersection point lies between the end points of the one line 
segment, it will lie between the end points of the other as well.)

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.

Jim