Testing to see if triangles intersect

532 Views Asked by At

i saw this question on reddit

I’m curious, because it was an interesting question, and would like someone to please clarify / help me determine if my statement is actually true.

this was my logic:

So by subtraction of co-ordinates and applying Pythagoras, they could use the co-ordinate values to ensure the distances are greater than s. Thanks. Are there any better ways of doing this?

2

There are 2 best solutions below

3
On BEST ANSWER

As rightly pointed out by @TobyMak one condition is to determine if any vertex of a triangle is, or is not, inside another triangle.
However, if all vertices of a triangle are outside another, this will also include the case that the two triangles intersects.

Triang_in_out_1

So we shall counter-test also for this condition, if overlapping shall be excluded.

Now to test if a point is external to a given triangle, we have better use the barycentric coordinates approach.

Given the triangle $ABC$ with vertices $(x_A, y_A),\, (x_B, y_B), \, (x_C, y_C)$ we construct the matrix $$ {\bf T} = \left( {\matrix{ {x_A } & {x_B } & {x_C } \cr {y_A } & {y_B } & {y_C } \cr 1 & 1 & 1 \cr } } \right) $$

A point $P=(x,y)$ will be internal to the triangle if its barycentric coordinates wrt $\triangle ABC$ are all positive, i.e. iff $$ \left( {\matrix{ {\lambda _{\,1} } \cr {\lambda _{\,2} } \cr {\lambda _{\,3} } \cr } } \right) = {\bf T}^{\, - \,{\bf 1}} \left( {\matrix{ x \cr y \cr 1 \cr } } \right) \quad \Rightarrow \quad 0 < \lambda _{\,1} ,\lambda _{\,2} ,\lambda _{\,3} $$

The $\lambda _k$ sum to $1$, so they cannot be all negative.
If one at least is negative, then the point $P$ is external.
And if it is $\lambda_1$ to be negative, then you know that $P$ is on the side of the edge $BC$ opposite to $A$.

So, if you take the $\triangle XYZ$ and modify its coordinates by a translation and a rotation $$ \eqalign{ & {\bf X} = \left( {\matrix{ {x_X } & {x_Y } & {x_Z } \cr {y_X } & {y_Y } & {y_Z } \cr 1 & 1 & 1 \cr } } \right)\quad \Rightarrow \cr & {\bf X}' = \left( {\matrix{ {\cos \alpha } & { - \sin \alpha } & 0 \cr {\sin \alpha } & {\cos \alpha } & 0 \cr 0 & 0 & 1 \cr } } \right)\left( {\left( {\matrix{ {x_X } & {x_Y } & {x_Z } \cr {y_X } & {y_Y } & {y_Z } \cr 1 & 1 & 1 \cr } } \right) + \left( {\matrix{ u & u & u \cr v & v & v \cr 0 & 0 & 0 \cr } } \right)} \right) \cr} $$ then by taking the product $$ {\bf \Lambda } = {\bf T}^{\, - \,{\bf 1}} \;{\bf X}' $$ you can adjust the parameters $\alpha, u, v$ in such a way that at least one component in every column of $\Lambda$ be negative, to ensure that all the vertices of $\triangle X'Y'Z'$ are external to $\triangle ABC$.

Finally, to test that the two triangles do not overlap, we take a generic point $Q$ internal to $\triangle X'Y'Z'$ $$ Q = {\bf X}'\, \left( {\matrix{ {\mu _{\,1} } \cr {\mu _{\,2} } \cr {\mu _{\,3} } \cr } } \right) \quad \left| \matrix{ \,0 \le \mu _{\,1} ,\mu _{\,2} ,\mu _{\,3} \left( { \le 1} \right) \hfill \cr \,\mu _{\,1} + \mu _{\,2} + \mu _{\,3} = 1 \hfill \cr} \right. $$ and test that not all the components of $$ {\bf T}^{\, - \,{\bf 1}} Q = {\bf T}^{\, - \,{\bf 1}} {\bf X}'\left( {\matrix{ {\mu _{\,1} } \cr {\mu _{\,2} } \cr {\mu _{\,3} } \cr } } \right) = {\bf \Lambda }\left( {\matrix{ {\mu _{\,1} } \cr {\mu _{\,2} } \cr {\mu _{\,3} } \cr } } \right) $$ are positive for any of the allowed values of $\mu _k$.

1
On

If at least one vertex $X, Y, Z$ is inside triangle $ABC$, then the triangles must intersect. This is because in the worst case, the distance from the centre (for example, the centroid) to any vertex is less than the side length, so the side of triangle $XYZ$ will protrude outside triangle $ABC$.

One possible way to check for this is to use Viviani's theorem, which states that the sum of (perpendicular) distances from the point to the sides is constant. If the sum of these distances of any vertex equals the altitude of the triangle, then the triangles intersect. (Note that this does not imply if the sum of the distances is not the altitude, the triangles don't intersect).

This, together with the condition you mentioned should cover all possible cases, as one condition checks if they do not intersect, and this condition checks if they intersect.