二维空间中三角形碰撞的检测

Question

如果两个三角形在2D坐标平面上的顶点,我怎么能以编程方式检测两个三角形是否相互接触？这包括触摸点或边缘,以及一个三角形是否完全在另一个内部.

Answer 1

您可以通过找到一条边（在构成两个三角形的总共 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

Answer 2

总之，哈桑的回答是最快的。

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 的边界框中。这大约与重心一样快。

这些就是工具。现在为了确定三角形是否相交，我测试了 3 种方法：

1. 8 条线相交和 2 个三角形内点：您只需要 8 条线相交，而不是全部 9 条，因为不可能只有 1 个相交。之后，您需要 2 个三角形内点，以防 1 个三角形完全位于另一个三角形内部。
2. 6条线相交和4个三角形内点：如果你把它画出来，你会发现你可以完全忽略其中一个三角形的一侧作为线相交，然后只做所有其他三角形点作为三角形内点。因为线相交和重心速度大致相同，所以这并不比#1 好多少。但如果你使用同边，它会更快，因为同边三角形点更慢。
3. 9 个同边三角形点测试：您可以使用重心或同边。对于任一情况，您都可以修改三角形中的点以同时测试 3 个点，并且您不想只测试它们是否全部位于三角形之外，您需要测试它们是否全部位于同一三角形的外部边。由于我们重复使用大量信息，因此可以节省计算时间。同样，重心似乎也比同侧快一些。

Answer 3

使用线 线相交

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