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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.