Solved

Need a calculation to check if 2 quadrangles overlap

Posted on 2009-05-06
5
312 Views
Last Modified: 2012-05-06
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.
The quadrangles are always convex.

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?
Thanks in advance.
mathproblem.jpg
0
Comment
Question by:Snapples
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 15

Expert Comment

by:David L. Hansen
ID: 24315350
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
 
LVL 15

Accepted Solution

by:
David L. Hansen earned 500 total points
ID: 24315459
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
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 24315996
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
 
LVL 20

Expert Comment

by:thehagman
ID: 24317484
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
 
LVL 20

Expert Comment

by:thehagman
ID: 24317514
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

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Complex Numbers are funny things.  Many people have a basic understanding of them, some a more advanced.  The confusion usually arises when that pesky i (or j for Electrical Engineers) appears and understanding the meaning of a square root of a nega…
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

733 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question