Overlapping Polygons

Date: 06/10/2003 at 08:35:32
From: Jagdish 
Subject: Find whether two polygons are overlapping in a 2d plane

I am trying to write a Java program. Given all the coordinates for two 
different polygons in an x,y plane, it must be able to determine 
whether the polygons overlap.  

Thanking you, 
Jagdish 

Date: 06/10/2003 at 09:23:29
From: Doctor George
Subject: Re: Find whether two polygons are overlapping in a 2d plane

Hi Jagdish,

Thanks for writing to Doctor Math.

The polygons overlap if a side of one polygon intersects a side of the 
other polygon.

Let's say that line L1 contains vertices V11 and V12 from one polygon, 
and line L2 contains vertices V21 and V22 from the other polygon.

We can write vector equations for L1 and L2 like this.

   L1 = V11 + a(V12 - V11)

   L2 = V21 + b(V22 - V21)

Where L1 and L2 intersect we must have

   V11 + a(V12 - V11) = V21 + b(V22 - V21)

         a(V12 - V11) = (V21  - V11) + b(V22 - V21)

Now define vector VP to be perpendicular to (V22 - V21) and take the 
dot product of both sides with VP.

   a[(V12 - V11).VP] = (V21 - V11).VP

Note that the b term has dropped out. If [(V12 - V11).VP] = 0 then 
L1 and L2 are parallel; otherwise we can solve for a. In a similar 
way we can also make a drop out and solve for b.

Now we need to work through this procedure for every combination of 
sides from the two polygons and make a list of all of the (a,b) pairs.

Here are the options.

1. If a and b are both in [0,1] for some (a,b), 
   then L1 intersects L2 at a point on both polygon edges.

2. If some a is in [0,1] and no b is in [0,1], 
   then the polygon with the a values contains the polygon 
   with the b values.

3. If no a is in [0,1] and some b is in [0,1], 
   then the polygon with the b values contains the polygon 
   with the a values.

4. If no a is in [0,1] and no b is in [0,1],
   then the polygons have no overlap.

Can you take it from here?  Write again if you need more help. 

- Doctor George, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 06/11/2003 at 00:35:17
From: Jagdish
Subject: Thank you 

Dear Sir,

I am very thankful for your reply to my query. I am sure that your 
solution is really going to help me.

Regards,
Jagdish
India