Point inside the area of two overlapped triangles

Question

The question is as simple as that, but I have been trying to figure out an answer (and searching for it) with 0 results. I mean, given two triangles (in 2D) I want to find just a single point which they may have in common. Of course I have the long solution consisting of looking for intersections in their perimeter. But maybe you could guide me to a faster solution for computing it.

For example, given the first triangle A(0,0) B(0,4) C(4,0) and the second A'(0,0) B'(2,4) C'(2,0) some possible solutions are : P(0,0) or P(1,1) or P(2,2) or P(1,2), ...

Summary: Im looking for a "fast" algorithm that given A, B, C, A', B', C' it outputs a single point P (if it exists) common to both triangles

Any ideas? Thanks

Answer 1

This is a harder problem than it might seem.

A Google search for "intersection of two triangles" came up with, among other suggestions, this, which handles both 2D and 3D triangles: https://hal.inria.fr/inria-00072100/file/RR-4488.pdf .

You can append "2D" to the search to restrict your results.

Answer 2

The idea is simple: find a point that is belonging to both triangle.

If there is an overlap, it means that at least one of the vertices of one triangle is inside the other.

To find if a point is in a triangle, you get the line equations for each edge and check for the sign when you insert the point and the third vertex (out of the three vertices) in the line equation. If the sign is the same that means that the point is in the same side. You do the test for all three combination and if you find that all tests result same sign, it means that the point is in the triangle.

To find the solution for your problem just pick any triangle and check if any of the vertices of the other triangle is in the triangle you selected. It is not important which triangle you pick first.

Then do the test with the other triangle (you might find the solution with the first one. I think that you can easily take it from here, if not will provide you the solution.

Answer 3

Depending on what kind of triangles you tend to get and how they are distributed, you might get some benefit by constructing a "bounding box" around each triangle, that is, for each triangle draw a rectangle with sides parallel to your coordinate axes so that the rectangle contains the entire triangle but is as small as possible. At least one vertex of the triangle will be at a corner of the rectangle, and the other two vertices will be at corners or on sides of the rectangle.

Two such rectangles overlap only if their $x$ coordinates overlap and their $y$ coordinates also overlap. This can be checked very quickly. If you have a lot of non-overlapping triangles with sufficient separation, you could efficiently eliminate them as candidates for intersection.

This procedure does not help you much if most of your triangles actually do intercept or if you have a lot of long, needle-shaped triangles all tilted approximately $45$ degrees to the right. It is only really useful if the bounding boxes are very likely not to overlap.