Erkennung von Dreieckskollision im 2D-Raum

Question

Wie kann ich programmgesteuert erkennen, ob sich zwei Dreiecke berühren, wenn ihre Scheitelpunkte auf einer 2D-Koordinatenebene liegen? Dies beinhaltet das Berühren von Punkten oder Kanten, sowie das Einpassen eines Dreiecks in das andere.

Answer 1

Verwenden Line Line Kreuzung

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

auch die Möglichkeit in Betracht ziehen, dass einige Vertex könnte einer der Seiten des anderen Dreiecks berühren.

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 

oder unter diesem Link sehen und nach unten scrollen

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

Answer 2

Sie nachweisen können, dass die beiden Dreiecke nicht kollidieren durch eine Kante zu finden (von den insgesamt 6 Kanten die die zwei Dreiecke bilden), die als eine Trennungslinie wirken, wo alle Eckpunkte eines Dreiecks auf der einen Seite liegen und die Eckpunkte des anderen Dreiecks auf der anderen Seite liegen. Wenn Sie eine solche Kante finden, dann bedeutet dies, dass die Dreiecke sich nicht schneiden, sonst kollidieren die Dreiecke.

Hier ist eine Matlab-Implementierung der Dreiecks-Kollisionsfunktion. Sie können die Theorie der sameside Funktion finden Sie hier: 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 3

Kurz gesagt, Hassan Antwort am schnellsten ist.

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

Dies ist der schnellste 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)); 
} 

ich die oben Geige schrieb ein paar verschiedene Techniken zu testen und die Geschwindigkeit zu vergleichen. Alle Techniken basieren auf einer Kombination von drei verschiedenen Werkzeugen:

1. Baryzentrische point-in-Dreieckstest: einen Punkt x Konvertieren, y Raum u, v-Raum, wobei u, v sind zwei Seiten das Dreieck. Dann teste, ob der Punkt innerhalb des Dreiecks (0,0) (0,1) (1,0) liegt, was einfach ist.
2. Gleichseitiger Punkt-in-Dreieck-Test: Dieser Test sagt Ihnen, ob ein Winkel mehr oder weniger als 180 Grad beträgt. Wenn das Dreieck a, b, c ist und Ihr Punkt p ist, prüfen Sie, ob die Winkel pab und bac beide mehr oder beide kleiner als 180 sind. Sie müssen dies für ab, bc und ca. Wenn etwas wahr ist, ist der Punkt draußen. Dieser Test ist langsamer als barycentric für einen Punkt.
3. Liniensegmentschnittpunkt: Überprüfen Sie, ob das Liniensegment a, b das Liniensegment c, d schneidet. Um dies zu tun, finden Sie den Punkt, wo sich die zwei Linien kreuzen und dann überprüfen, dass diese Linien in der Bounding Box von a, b und b, c sind. Das ist ungefähr so ​​schnell wie Barycentric.

Das sind die Werkzeuge.Nun, um herauszufinden, ob Dreiecke schneiden, gibt es drei Möglichkeiten, die ich getestet:

1. 8 Linie Kreuzung und 2-Punkt-in-Dreieck: Sie haben nur 8 Linie Kreuzung müssen und nicht alle 9 denn es kann nicht sei nur 1 Kreuzung. Danach brauchen Sie 2 Punkt-in-Dreieck, falls ein Dreieck vollständig innerhalb des anderen liegt.
2. 6-Linien-Schnittpunkt und 4 Punkt-in-Dreieck: Wenn Sie es herausziehen, können Sie sehen, dass Sie eine Seite eines der Dreiecke für Linienschnitt vollständig ignorieren können und dann nur alle anderen Dreiecke Punkte für Punkt-in-Dreieck. Da Linienkreuzung und Baryzentrik ungefähr gleich schnell sind, ist dies nicht viel besser als # 1. Aber wenn Sie die gleiche Seite verwenden, wird es schneller sein, da der gleiche Punkt in Dreiecksrichtung langsamer ist.
3. 9 gleichseitige Punkt-in-Dreieck-Tests: Sie können entweder baryzentrische oder gleiche Seite verwenden. Für beide, Sie ändern den Punkt-in-Dreieck, um 3 Punkte gleichzeitig zu testen und Sie möchten nicht nur testen, dass sie alle drei außerhalb des Dreiecks sind, müssen Sie testen, dass sie alle 3 außerhalb auf der gleiche Seite. Da wir viele Informationen erneut verwenden, können wir bei den Berechnungen Zeit sparen. Auch hier wirkt Baryzentrik etwas schneller als die gleiche Seite.