Détection de Triangle de Collision dans l'Espace 2D

Utiliser la Ligne d'intersection des droites

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

Également envisager la possibilité que certains vertex peut être en contact avec l'un des côtés de l'autre 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

Ou regardez ce lien et faites défiler vers le bas

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

OriginalL'auteur Hamish Grubijan

En bref, la réponse de Hassan est la plus rapide.

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

C'est le plus rapide de code en 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));
}

J'ai écrit ci-dessus de violon pour tester quelques techniques différentes et de comparer la vitesse. Toutes les techniques sont basées sur une combinaison de trois outils différents:

1. Barycentriques du point-à-triangle test: Convertir un point de l'espace x,y u,v espace où u,v sont deux des côtés du triangle. Puis tester si le point est à l'intérieur du triangle (0,0) (0,1) (1,0), ce qui est facile.
2. Même côté du point-à-triangle test: Ce test vous indique si un angle est plus ou moins de 180 degrés. Si le triangle a,b,c et votre point de p, - vous vérifier si l'angle de cap et de bac sont à la fois plus ou moins de 180. Vous devez faire cela pour ab, bc et ca. Si tout est vrai, le point est à l'extérieur. Ce test est plus lent que barycentriques pour un point.
3. Segment de ligne d'intersection: Vérifier si le segment a,b coupe la droite du segment c,d. Pour ce faire, vous trouver le point où les deux lignes se croisent et ensuite vérifier que ces lignes sont dans la boîte englobante de a,b et b,c. C'est presque aussi rapide que la Barycentriques.

Ceux sont les outils. Maintenant à savoir si les triangles se croisent, il y a 3 façons que j'ai testé:

1. 8 la ligne d'intersection et de 2 points en triangle: Vous n'avez besoin que de 8 ligne d'intersection et pas tous les 9 car il ne peut pas être juste 1 intersection. Après cela, vous avez besoin de 2 points en triangle dans le cas 1 triangle est entièrement à l'intérieur de l'autre.
2. 6 ligne d'intersection et de 4 points en triangle: Si vous dessinez, vous pouvez voir que vous pouvez ignorer complètement un côté de l'un des triangles pour la ligne d'intersection et puis il suffit de faire tous les triangles points de point-à-triangle. Parce que la ligne d'intersection et barycentriques sont sur la même vitesse, ce n'est pas beaucoup mieux que le #1. Mais si vous avez utilisé du même côté, il sera plus rapide, car même côté du point-à-triangle est plus lent.
3. 9 du même côté du point-à-triangle tests: Vous pouvez utiliser soit barycentrique ou même côté. Soit, vous de modifier le point-à-triangle de test de 3 points dans le même temps, et vous ne voulez pas de simplement vérifier qu'ils sont tous les trois à l'extérieur du triangle, vous devez vérifier qu'ils sont tous les 3 en dehors de sur le même côté. Parce que nous sommes re-à l'aide d'un grand nombre d'informations, nous pouvons gagner du temps dans les calculs. Encore une fois, barycentriques semble légèrement plus rapide que le même côté d'ici, trop.

OriginalL'auteur Eyal