x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 328

# Need a calculation to check if 2 quadrangles overlap

Below is a little graph with an example.
I have 2 quadrangles and I know every point location of both of them.
Now I'd need a calculation that lets me check if they overlap or not.

I came as far as this:
if the minimum x value of quad2 is higher than the maximum x value of quad1 or the maximum x value of quad2 is smaller than the minimum x value of quad1, they can never overlap
if the minimum y value of quad2 is higher than the maximum y value of quad1 or the maximum y value of quad2 is smaller than the minimum y value of quad1, they can never overlap

but that's not enough, the blue quadrangle passes these 2 criteria and yet it doesn't overlap with the black one.
Anyone got an idea?
mathproblem.jpg
0
Snapples
• 2
• 2
1 Solution

Programmer AnalystCommented:
Try this
http://pesona.mmu.edu.my/~ypwong/yr1999sem2/tcs2111cg/note9.PDF

search on: "To determine if a point P is within a polygon" and you'll find the passage.
0

Programmer AnalystCommented:
It sounds like you determine a line from each point in your polygon (in your case quadrangle) to the point P in question, thus forming four adjoining triangles.  Then just calculate the area of each and sum those all together.  If the resulting area is equal to the area of the original quadrangle then point P does lie within the quadrangle, if not, it lies outside of it.
0

Commented:
Just detecting whether a corner is in the polygon is not good enough.  Imagine you have two long narrow quadrangles forming a cross.

The separating axis method is robust and easy enough to implement.  See http://gpwiki.org/index.php/Polygon_Collision
0

Commented:
Two quadrangels are disjoint iff no two edges intersect --  there are only 16 intersections to check.
To check whether AB intersects CD,
compare the signs of   (D-A) x (B-A)  and  (C-A) x (B-A) -- if they are the same, no intersection occurs
then compare the signes of (A-C) x (D-C) and (B-C) x (D-C) -- if they are the same, no intersection occurs
If none of these two tests hinted at "no intersection", then the segments *do* intersect.
(In the above, (D-A) x (B-A) stands for  (xD-xA)*(yB-yA) - (yD-yA)*(xB-xA) etc.)
0

Commented:
Oops, forgot the case of one quadrangle completely containing the other.
To take care of that, check for a single vertex of one whether it is inside the other and also vice versa
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.