Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

see title.

assume we are given two parallelograms in the plane. how can I check if the intersection is nonempty?

note that I do not need to actually find the intersection.

share|improve this question
1  
I would use a sweep line algorithm, if a hasd to program such a program. This should have the advantage, that it works in general for any polygon. en.wikipedia.org/wiki/Sweep_line_algorithm –  HenrikRüping Sep 16 '10 at 9:56
add comment

3 Answers

Given two convex sets $A$ and $B$ in a vector space, their intersection is not empty iff the difference set $A-B=\{p-q|p\in A, q\in B\}$ contains the origin. In your setting the difference set is the convex hull of 16 points. Actually 8 of them are enough and you have to check that 0 is on the same side of any of the 8 edges than the difference convex polygon.

share|improve this answer
    
Very clever! $\mbox{}$ –  Joseph O'Rourke Sep 16 '10 at 12:46
1  
Impressive observation. Isn't this more computationally intensive than Joseph's approach here? Or is it possible to translate polygon $A$ by the vertices of $B$ one at a time, and check to see if the origin is contained within the translated polygon $A_{Bi}$ ? (where $B_i$ stands for each of the vertices of polygon $B$) –  sleepless in beantown Sep 16 '10 at 13:04
    
no, this is not possible, unfortunately. –  Philipp Sep 17 '10 at 15:08
add comment

I don't think there is a simple criterion, no, assuming your parallelograms are arbitrary. An approach less general than that suggested by HenrikRüping, but likely easier to code is this. Check if one of the four vertices of $A$ is inside $B$. If so, return yes. Next check each edge of $A$ for intersection with each edge of $B$. If an edge intersection is detected, return yes. If all these tests fail, return no. How to perform the primitive intersection tests is all over the web, and in particular here.

share|improve this answer
3  
wouldn't you also have to check to see if $B$ is inside $A$? –  sleepless in beantown Sep 16 '10 at 13:00
1  
@sleepless: Whoops! You are correct. My oversight. Thanks for noticing. Actually, as Vagabond says, it would suffice to check if one vertex of A is in B, and one vertex of B in A, and then perform the edge-intersection tests. –  Joseph O'Rourke Sep 16 '10 at 14:29
add comment

Observe Two parallelogram $A$ and $B$ can intersect if and only if one edge of $A$ and one edge of $B$ intersects (crosses over) unless one parallelogram is sitting inside the other.

I am assuming the second case does not happen.

So the problem reduces to answering when does two line segment of finite edges intersect.

Here is how to check ...

Take edge $A_{12}$ joing $a_1$ to $a_2$ and $B_{34}$ joining $b_3$ to $b_4$

so in order to check if $A_{12}$ intersects $B_{34}$

take the line defined by $A_{12}$, $b_3$ and $b_4$ should lie on two different sides of this and further ${a_1}, {a_2}$ should lie on opposite side of $B_{34}$.

So one check this by taking some inner products .... we need to check if appropriate sign change happens ...(intermediate value theorem) if it does then lines cross.

share|improve this answer
    
ok! I realise its identical to Joseph O'Rourke's solution. –  Vagabond Sep 16 '10 at 13:53
    
Not quite identical, your observation implies that only one point-in-parallelogram test need be made for A in B and one for B in A. –  Joseph O'Rourke Sep 16 '10 at 14:35
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.