Assume we are given two parallelograms in the plane. How can I check if their intersection is nonempty?
Note that I do not need to actually find the intersection.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ 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 $\endgroup$– HenrikRüpingCommented Sep 16, 2010 at 9:56
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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.
answered Sep 16, 2010 at 12:23
-
-
1$\begingroup$ 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$) $\endgroup$ Commented Sep 16, 2010 at 13:04
-
$\begingroup$ no, this is not possible, unfortunately. $\endgroup$– PhilippCommented Sep 17, 2010 at 15:08
$\begingroup$
$\endgroup$
2
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, including here.
answered Sep 16, 2010 at 10:26
-
3$\begingroup$ wouldn't you also have to check to see if $B$ is inside $A$? $\endgroup$ Commented Sep 16, 2010 at 13:00
-
1$\begingroup$ @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. $\endgroup$ Commented Sep 16, 2010 at 14:29
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ ok! I realise its identical to Joseph O'Rourke's solution. $\endgroup$– VagabondCommented Sep 16, 2010 at 13:53
-
$\begingroup$ 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. $\endgroup$ Commented Sep 16, 2010 at 14:35