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

Question

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

mathgeometrycollision-detection

14

如何以编程的方式检测两个三角形是否相互接触，给出它们在二维坐标系上的顶点？这包括触碰点或边缘，以及一个三角形是否完全位于另一个三角形内部。

- qJake

1

看起来很像这个问题的重复：https://dev59.com/x0rSa4cB1Zd3GeqPZdL6那是关于三维而不是二维的，但也许那里的一些答案会对你有所帮助。 - bcat

2

我已经查看了那个问题，它似乎比我需要的信息要多得多，因为它是针对3D特定情况的，而我不想在这里过度复杂化计算（这些计算将在循环中执行，并且应尽可能具有成本效益）。 - qJake

1

可能是如何检测三角形相交的最有效方法？的重复问题。 - TimSC

3个回答

6

简而言之，Hassan的答案是最快的。 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. 线段交集：检查线段ab是否与线段cd相交。为此，您需要找到两条线相交的点，然后检查这些线是否在ab和bc的边界框内。这与重心点测试的速度差不多快。

以上是三种工具。现在要找出三角形是否相交，我测试了3种方法：

1. 8条线相交和2个点在三角形内：您只需要8条线相交，而不是全部9条，因为不能只有1个交点。之后，如果一个三角形完全在另一个三角形内，则需要2个点在三角形内。 2. 6条线相交和4个点在三角形内：如果您将其画出来，就会看到您可以完全忽略其中一个三角形的一侧进行线相交，然后只需对另一个三角形的所有其他点进行点在三角形内测试。因为线相交和重心点测试速度相当，所以这比方案1好不了多少。但是，如果使用同侧测试，那么速度会更快，因为同侧点在三角形内测试较慢。 3. 9个同侧点在三角形内测试：您可以使用重心点或同侧。对于任一种方法，您都要将点在三角形内测试修改为同时测试3个点，并且您不仅要测试它们是否全部在三角形外面，还要测试它们是否全部在同一侧的外部。由于我们正在重复使用很多信息，因此可以节省计算时间。同样，重心点似乎在此处略微快于同侧。

- Eyal

你如何找到交点，又如何排除相同的点？ - synchronizer

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

这篇文章涉及IT技术，点击链接可获取更多信息。

- Hamish Grubijan

5

这个并不检查一个三角形是否完全在另一个三角形内部，对吗？ - qJake

@SpikeX：我也想说同样的话，但我认为你需要点击底部的链接查找PointInPolygon的写作（http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry3）。 - Dave

为此，您需要确保所有3个顶点都在三角形的边缘或内部。让我找一个链接。同时，随意点赞。 - Hamish Grubijan

好吧，这可能不太美观，但我可以将您的“PointInTriangle”函数与Line-Line检测函数结合起来，以获得我所需的内容。（我的第一条评论是在帖子被编辑之前发表的）。谢谢。 - qJake

1

很棒。如果你想在可读性的代价上使其超级优化，考虑在着手修改代码之前先编写单元测试。 - Hamish Grubijan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Hassan · Accepted Answer

你可以通过找到一条边（总共6条边），该边作为一个分离线，其中一个三角形的所有顶点位于一侧，另一个三角形的顶点位于另一侧，来证明两个三角形不会相交。如果你能找到这样一条边，则意味着三角形不相交，否则它们会相撞。

以下是triangle collision函数的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