Intersection of two right triangles [closed]

Here is the code for arbitrary triangles. He wrote on his knee, but everything seems to be working.

Homework:

1. Find out if you can somehow optimize the algorithm, knowing that the triangles are rectangular.
2. Get rid of multiple calculations GetWinding for the same triples of points.

 #include <iostream> #include <utility> struct Point {float x, y;}; struct Triangle {Point points[3];}; // Знак возвращаемого значения показывает, с какой стороны (слева или справа) // точка C находится от вектора AB. float GetWinding(Point a, Point b, Point c) { // Находятся вектора AB и AC. Дополняются до трехмерных добавлением Z = 0. // Вычисляется их векторное произведение, от которого берется только // Z-координата. float x1 = bx - ax, y1 = by - ay; float x2 = cx - ax, y2 = cy - ay; return x1 * y2 - x2 * y1; } // Изменяет треугольник ABC так, чтобы GetWinding(A,B,C) было >= 0. // Если это условие уже выполняется, треугольник возвращается без изменений. // Иначе точки B и C меняются местами. Triangle FixWinding(Triangle tri) { if (GetWinding(tri.points[0], tri.points[1], tri.points[2]) < 0) std::swap(tri.points[1], tri.points[2]); return tri; } // Проверяет, находится ли точка внутри треугольника. // Предполагается, что к треугольнику уже была применена FixWinding(). bool PointTriangleCollision(Point p, Triangle tri) { return GetWinding(tri.points[0], tri.points[1], p) >= 0 && GetWinding(tri.points[1], tri.points[2], p) >= 0 && GetWinding(tri.points[2], tri.points[0], p) >= 0; } // Проверяет два отрезка A и B на пересечение. bool EdgeEdgeCollision(Point a1, Point a2, Point b1, Point b2) { return GetWinding(a1, a2, b1) * GetWinding(a1, a2, b2) <= 0 && GetWinding(b1, b2, a1) * GetWinding(b1, b2, a2) <= 0; } // Проверяет два треугольника на пересечение. // Предполагается, что к треугольникам уже была применена FixWinding(). bool TriangleTriangleCollision(Triangle a, Triangle b) { // Если хотя бы один угол одного треугольника внутри // другого треугольника, то пересечение есть. for (int i = 0; i < 3; i++) { if (PointTriangleCollision(a.points[i], b)) return 1; if (PointTriangleCollision(b.points[i], a)) return 1; } // Если хотя бы одна пара ребер разных треугольников // пересекается, то треугольники пересекаются. for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { int i_next = (i + 1) % 3; int j_next = (j + 1) % 3; if (EdgeEdgeCollision(a.points[i], a.points[i_next], b.points[j], b.points[j_next])) return 1; } // Иначе - нет пересечения. return 0; } // Делает то же, что TriangleTriangleCollision(), но сама // применяет FixWinding к аргументам. bool TriangleTriangleTest(Triangle a, Triangle b) { return TriangleTriangleCollision(FixWinding(a), FixWinding(b)); } int main() { std::cout << TriangleTriangleTest({{{1,1},{3,1},{1,3}}}, {{{11,11},{11,10},{10,11}}}) << '\n'; std::cout << TriangleTriangleTest({{{1,1},{3,1},{1,3}}}, {{{1.5,1.5},{10,9},{9,10}}}) << '\n'; std::cout << TriangleTriangleTest({{{1,1},{3,1},{1,3}}}, {{{2,2},{2,2.1},{2.1,2}}}) << '\n'; std::cout << TriangleTriangleTest({{{-3,2},{3,2},{0,-4}}}, {{{3,-2},{-3,-2},{0,4}}}) << '\n'; } 

What kind of "intersection" are we talking about? Crossing triangular areas? Or the intersection of the boundaries of triangular areas? If one triangle lies entirely inside the other - is it an intersection or not?

I assumed that a situation when one triangle is entirely inside another is considered to be an intersection. If this is not the case, then remove the first half of TriangleTriangleCollision() and all related functions.

The separating axis method ( Separating axis theorem , more ) works for any convex polygons, incl. and for triangles

It is likely to be close in efficiency to the direct method that checks the intersection of each side of one triangle with the two sides of the other (based on the signs of the vector product) + test for complete occurrence.

Perhaps in a specific task there are additional conditions that will allow to organize a simpler check (although the SAT method is simple)

How can I use the triangular triangles - I do not know. I suspect that at the level of the general task it is impossible to take advantage of this and it will be necessary to solve the problem for arbitrary triangles. (At the level of internal computing, it is possible that something will be optimized.)

If we are talking about the detection of the intersection of triangular regions A and B , then such an intersection exists if the boundaries of the regions intersect or one region lies inside the other. This gives us the following (enough frontal check algorithm)

1. Each side of triangle A checked for intersection with each side of triangle B To do this, it will be necessary nine times ( maximum nine times) to check for the intersection of two segments . If an intersection is found, then the triangles intersect.

2. Otherwise, take some internal point of triangle A and check if it is inside of triangle B And vice versa: we take some inner point of triangle B and check if it is inside triangle A If one of these two checks detects a point lying inside, then the triangles intersect.

As usual in such cases, a decision should be made on how to assess border situations, i.e. touch triangles.