Detection of Triangle Collision in 2D Space

How can I programmatically detect whether or not two triangles touch each other, given their vertices on a 2D coordinate plane? This includes touching points or edges, as well 开发者_如何学JAVAas if one triangle is completely inside the other one.

You can prove that the two triangles do not collide by finding an edge (out of the total 6 edges that make up the two triangles) that acts as a separating line where all the vertices of one triangle lie on one side and the vertices of the other triangle lie on the other side. If you can find such an edge then it means that the triangles do not intersect otherwise the triangles are colliding.

Here is a Matlab implementation of the triangle collision function. You can find the theory of the sameside function here: 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

In short, Hassan's answer is fastest.

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

This is the fastest code in 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));
}

I wrote the above fiddle to test a few different techniques and compare the speed. All the techniques are based on some combination of three different tools:

1. Barycentric point-in-triangle test: Convert a point from x,y space to u,v space where u,v are two sides of the triangle. Then test if the point is inside the triangle (0,0) (0,1) (1,0), which is easy.
2. Same-side point-in-triangle test: This test tells you if an angle is more or less than 180 degrees. If the triangle is a,b,c and your point is p, you check if the angle pab and bac are both more or both less than 180. You need to do this for ab, bc, and ca. If any are true, the point is outside. This test is slower than barycentric for one point.
3. Line segment intersection: Check if the line segment a,b intersects line segment c,d. To do that, you find the point where the two lines cross and then check that those lines are in the bounding box of a,b and b,c. This is about as fast as Barycentric.

Those are the tools. Now to find out if triangles intersect, there are 3 ways that I tested:

1. 8 line intersection and 2 point-in-triangle: You only need 8 line intersection and not all 9 because there can't be just 1 intersection. After that, you need 2 point-in-triangle in case 1 triangle is entirely inside the other.
2. 6 line intersection and 4 point-in-triangle: If you draw it out, you can see that you can completely ignore one side of one of the triangles for line intersection and then just do all the other triangles points for point-in-triangle. Because line intersection and barycentric are about the same speed, this isn't much better than #1. But if you used same-side, it will be faster because same side point-in-triangle is slower.
3. 9 same-side point-in-triangle tests: You can use either barycentric or same side. For either, you modify the point-in-triangle to test 3 points at the same time and you don't want to just test that they are all three outside the triangle, you need to test that they are all 3 outside on the same side. Because we're re-using a lot of information, we can save time in calculations. Again, barycentric seems slightly faster than same side here, too.

Use Line Line intersection

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

Also consider the possibility that some vertex might be touching one of the sides of the other triangle.

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

Or look at this link and scroll down

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