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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityAssume 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.
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.
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.
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.