Обнаружение столкновения треугольников в 2D-пространстве

Использовать линию пересечения линии

https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-line-intersection-and-its-applications/#line_line_intersection

Также рассмотрите возможность того, что какая-то вершина может касаться одной из сторон другого треугольника.

http://www.blackpawn.com/texts/pointinpoly/default.html

function SameSide(p1,p2, a,b)
    cp1 = CrossProduct(b-a, p1-a)
    cp2 = CrossProduct(b-a, p2-a)
    if DotProduct(cp1, cp2) >= 0 then return true
    else return false

function PointInTriangle(p, a,b,c)
    if SameSide(p,a, b,c) and SameSide(p,b, a,c)
        and SameSide(p,c, a,b) then return true
    else return false

Или посмотрите эту ссылку и прокрутите вниз

http://compsci.ca/v3/viewtopic.php?t=6034

Вы можете доказать, что два треугольника не сталкиваются, найдя ребро (из всех 6 ребер, составляющих два треугольника), которое действует как разделяющая линия, где все вершины одного треугольника лежат на одной стороне, а вершины другой треугольник лежит на другой стороне. Если вы можете найти такое ребро, это означает, что треугольники не пересекаются, иначе треугольники сталкиваются.

Вот реализация Matlab функции столкновения треугольников. Вы можете найти теорию функции sameside здесь: http://www.blackpawn.com/texts/pointinpoly/default.html

function flag = triangle_intersection(P1, P2)
% triangle_test : returns true if the triangles overlap and false otherwise

% P1, P2: a 3 by 2 array (each), describing the vertices of a triangle,
% the first column corresponds to the x coordinates while the second column
% corresponds to the y coordinates

    function flag = sameside(p1,p2,a,b)
        % sameside : returns true if the p1,p1 lie on same sides of the
        % edge ab and false otherwise

        p1(3) = 0; p2(3) = 0; a(3) = 0; b(3) = 0;
        cp1 = cross(b-a, p1-a);
        cp2 = cross(b-a, p2-a);
        if(dot(cp1, cp2) >= 0)
            flag = true;
        else
            flag = false;
        end
    end

% Repeat the vertices for the loop
P1(4:5,:) = P1(1:2,:);
P2(4:5,:) = P2(1:2,:);

flag = true;

% Testing all the edges of P1
for i=1:3
    if(~sameside(P1(i,:), P2(1,:), P1(i+1,:), P1(i+2,:)) ...
            && sameside(P2(1,:), P2(2,:), P1(i+1,:), P1(i+2,:)) ...
            && sameside(P2(2,:), P2(3,:), P1(i+1,:), P1(i+2,:)))
        flag = false; return;
    end
end

% Testing all the edges of P2
for i=1:3
    if(~sameside(P2(i,:), P1(1,:), P2(i+1,:), P2(i+2,:)) ...
            && sameside(P1(1,:), P1(2,:), P2(i+1,:), P2(i+2,:)) ...
            && sameside(P1(2,:), P1(3,:), P2(i+1,:), P2(i+2,:)))
        flag = false; return;
    end
end

end

Короче говоря, ответ Хасана самый быстрый.

https://jsfiddle.net/eyal/gxw3632c/

Это самый быстрый код в javascript:

// check that all points of the other triangle are on the same side of the triangle after mapping to barycentric coordinates.
// returns true if all points are outside on the same side
var cross2 = function(points, triangle) {
  var pa = points.a;
  var pb = points.b;
  var pc = points.c;
  var p0 = triangle.a;
  var p1 = triangle.b;
  var p2 = triangle.c;
  var dXa = pa.x - p2.x;
  var dYa = pa.y - p2.y;
  var dXb = pb.x - p2.x;
  var dYb = pb.y - p2.y;
  var dXc = pc.x - p2.x;
  var dYc = pc.y - p2.y;
  var dX21 = p2.x - p1.x;
  var dY12 = p1.y - p2.y;
  var D = dY12 * (p0.x - p2.x) + dX21 * (p0.y - p2.y);
  var sa = dY12 * dXa + dX21 * dYa;
  var sb = dY12 * dXb + dX21 * dYb;
  var sc = dY12 * dXc + dX21 * dYc;
  var ta = (p2.y - p0.y) * dXa + (p0.x - p2.x) * dYa;
  var tb = (p2.y - p0.y) * dXb + (p0.x - p2.x) * dYb;
  var tc = (p2.y - p0.y) * dXc + (p0.x - p2.x) * dYc;
  if (D < 0) return ((sa >= 0 && sb >= 0 && sc >= 0) ||
                     (ta >= 0 && tb >= 0 && tc >= 0) ||
                     (sa+ta <= D && sb+tb <= D && sc+tc <= D));
  return ((sa <= 0 && sb <= 0 && sc <= 0) ||
          (ta <= 0 && tb <= 0 && tc <= 0) ||
          (sa+ta >= D && sb+tb >= D && sc+tc >= D));
}

var trianglesIntersect4 = function(t0, t1) {
  return !(cross2(t0,t1) ||
           cross2(t1,t0));
}

Я написал приведенную выше скрипку, чтобы протестировать несколько различных техник и сравнить скорость. Все техники основаны на комбинации трех разных инструментов:

1. Барицентрический тест точки в треугольнике. Преобразуйте точку из пространства x, y в пространство u, v, где u, v - две стороны треугольника. Затем проверьте, находится ли точка внутри треугольника (0,0) (0,1) (1,0), что легко.
2. Проверка точки в треугольнике на одной стороне: этот тест показывает, составляет ли угол больше или меньше 180 градусов. Если треугольник - это a, b, c, а ваша точка - p, вы проверяете, оба ли угла pab и bac больше или меньше 180. Это нужно сделать для ab, bc и ca. Если таковые имеются, то дело во внешнем. Этот тест медленнее, чем барицентрический для одной точки.
3. Пересечение отрезка прямой. Убедитесь, что отрезок a, b пересекает отрезок c, d. Для этого вы находите точку пересечения двух линий, а затем проверяете, находятся ли эти линии в ограничивающей рамке a, b и b, c. Это примерно так же быстро, как Barycentric.

Это инструменты. Теперь, чтобы узнать, пересекаются ли треугольники, я испытал 3 способа:

1. 8 линий пересечения и 2 точки в треугольнике: вам нужно только 8 пересечений линий, а не все 9, потому что не может быть только 1 пересечение. После этого вам понадобятся 2 точки в треугольнике, если один треугольник полностью находится внутри другого.
2. 6 линий пересечения и 4 точки в треугольнике: если вы начнете рисовать, вы увидите, что можете полностью игнорировать одну сторону одного из треугольников для пересечения линий, а затем просто сделать все остальные треугольники. точки за точку в треугольнике. Поскольку пересечение линий и барицентрическая скорость примерно одинаковы, это не намного лучше, чем №1. Но если вы использовали одну и ту же сторону, это будет быстрее, потому что точка в треугольнике с той же стороной работает медленнее.
3. 9 тестов точки в треугольнике с одинаковой стороной: можно использовать барицентрическую или одинаковую сторону. В любом случае вы модифицируете точку в треугольнике, чтобы проверять 3 точки одновременно, и вы не хотите просто проверять, что все три точки находятся за пределами треугольника, вам нужно проверить, что все они 3 за пределами на той же стороне. Поскольку мы повторно используем много информации, мы можем сэкономить время на вычислениях. Опять же, барицентрическая система кажется немного быстрее, чем та же сторона и здесь.