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

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

8 голосов
/ 06 мая 2010

Как я могу программно определить, касаются ли два треугольника друг друга, учитывая их вершины на 2D координатной плоскости? Это включает в себя точки соприкосновения или края, а также если один треугольник полностью находится внутри другого.

Ответы [ 3 ]

4 голосов
/ 24 июля 2016

Вы можете доказать, что два треугольника не сталкиваются, найдя ребро (из 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
2 голосов
/ 30 мая 2017

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

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 точки в треугольнике, если 1 треугольник находится полностью внутри другого.
  2. 6 пересечений линий и 4 точки в треугольнике : Если вы вытянете его, вы увидите, что можете полностью игнорировать одну сторону одного из треугольников для пересечения линий, а затем просто сделать все другие точки треугольников для точки в треугольнике. Поскольку пересечение линий и барицентрическое движение имеют примерно одинаковую скорость, это не намного лучше, чем № 1. Но если вы использовали ту же сторону, это будет быстрее, потому что точка-треугольник той же стороны медленнее.
  3. 9 тесты точки-треугольника на одной стороне : Вы можете использовать барицентрическую или ту же сторону. Для любого из них вы изменяете точку в треугольнике, чтобы тестировать 3 точки одновременно, и вы не хотите просто проверять, что все они находятся за пределами треугольника, вам нужно проверить, что все они находятся за пределами на той же стороне . Поскольку мы повторно используем много информации, мы можем сэкономить время в расчетах. Опять же, барицентрический здесь тоже немного быстрее, чем та же сторона.
2 голосов
/ 06 мая 2010

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

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

...