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 as if one triangle is completely inside the other one.
The most basic way to approach this type of 2d collision detection is to utilize a concept known as Axis-aligned bounding box. Axis-aligned bounding box, or AABB, detects if two non-rotational polygons are overlapping each other.
If both the horizontal and vertical edges overlap we have a collision. We check if the right side of the first object is greater than the left side of the second object and if the second object's right side is greater than the first object's left side; similarly for the vertical axis.
Collision detection concerns the detection of collisions between objects in the virtual environment. Primarily employed to stop objects moving through each other and the environment. Collision Detection is everywhere in computer games: between characters and characters, between characters and terrain, etc.
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:
Those are the tools. Now to find out if triangles intersect, there are 3 ways that I tested:
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
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With