Comment implémenter la détection de collision de polyligne Javascript

Question

J'ai actuellement un jeu de plateforme JavaScript. J'ai créé une détection de collision polygone-polygone avec une réponse, en utilisant la méthode SAT décrite sur de nombreux autres sites Web.

J'ai également créé une fonction dans le constructeur Polygon qui retournera soit les côtés exposés au sommet du polygone, soit les côtés exposés au fond du polygone, selon la direction choisie. Le tableau qui est retourné contient de nombreux vecteurs différents, qui seront expliqués plus en détail plus tard.

Le code actuel ressemble un peu à ceci:

Polygon.prototype.getSidesOn = function(dir) { 
    if (dir === "top" || dir === "bottom") { 
    var result = [], start = false, stop = false, elen = 
this.calcPoints.length, e = 0, f = 0, point, next, prevX, prevY, directionX, directionY; 
    while (!stop) { 
     if (e >= 5*elen) {return;} 
     f = e%elen; 
     prev = f-1 < 0 ? this.calcPoints[elen-1] : this.calcPoints[f-1]; 
     point = this.calcPoints[f]; 
     prevX = directionX; 
     prevY = directionY; 
     directionX = point.x > prev.x ? "right" : point.x < prev.x ? "left" : directionX; 
     directionY = point.y < prev.y ? "up" : point.y > prev.y ? "down" : directionY; 
     if (prevX !== directionX && prevX && prevY) { 
     if (!start) { 
      start = dir === "top" ? directionY === "up" : directionY === "down"; 
     } else { 
      break; 
     } 
     } 
     if (start) { 
     if (point.x !== prev.x) { 
      if (!result.length) { 
      result.push(new Vector(prev.x,prev.y),new 
Vector(point.x,point.y)); 
      } else { 
      result.push(new Vector(point.x,point.y)); 
      } 
     } else { 
      break; 
     } 
     } 
     e++; 
    } 
    return result; 
    } else { 
    return; 
    } 
} 

Je comprends qu'il est un peu en désordre, mais ce n'est pas un souci que j'optimiser plus tard. Fondamentalement, il fonctionne UNIQUEMENT sur des polygones convexes (je veux dire le mot "convexe" comme dans un triangle ou une forme qui ne rentre pas dans lui-même). Quoi qu'il en soit, cela fonctionne en raison du fait que tous les polygones convexes ont seulement deux points où les côtés adjacents font face à la direction X opposée.

Quoi qu'il en soit, le tableau qui ressemble un peu sorti comme ceci:

//[Vector,Vector,Vector,Vector...] 

qui n'est pas ce qu'il ressemble vraiment, mais au fond, il émet un tableau de vecteurs pour chaque point détecté.

Ce que j'ai besoin de mettre en œuvre est un moyen de détecter la collision entre deux de ces polylignes. Contrairement au système de détection de collisions polygone-polygone, il n'est pas nécessaire d'avoir un vecteur de réponse, et le code devrait plutôt afficher un booléen "vrai" ou "faux".

La seule façon que je peux actuellement penser à faire est la suivante:

function PolylinePolyline(line1,line2) { 
    var i, ilen = line1.length, j, jlen = line2.length; 
    for (i = 0; i < ilen; i++) { 
    for (j = 0; j < jlen; j++) { 
     var point1 = line1[i]; 
     var point2 = i+1 < ilen ? line1[i+1] : line1[0]; 
     var point3 = line2[j]; 
     var point4 = j+1 < jlen ? line2[j+1] : line2[0]; 
     var line01 = new line(point1,point2); 
     var line02 = new line(point3,point4); 
     if (LineLine(line01,line02) { 
     return true; 
     } 
    } 
    } 
    return false; 
} 

Et bien que cela fonctionne, il est très coûteux à utiliser si les lignes sont, disons, 5 points de long, et Je dois détecter une collision entre 4 d'entre eux. Je préférerais une alternative qui retourne vrai si elles sont en collision et fausse sinon. Je ne vais pas vous expliquer pourquoi je besoin de cela, car il est un peu abstrait, mais un exemple de polyligne serait ceci:

Note that the polylines are convex-shaped

Answer 1

Vous pouvez accélérer votre recherche de collision en définissant des lignes de longueur infinie (pseudo aléatoires) qui vont entre deux polygones de sorte que la ligne sépare les polygones en 3 ensembles: au-dessus, en dessous et en collision. Parce qu'ils sont détruits par la ligne, vous savez que tout ce qui précède ne se heurte pas à tout ce qui est en bas. Répétez ceci plusieurs fois jusqu'à ce que vous ayez un faible nombre de paires de polygones non résolues, puis appliquez votre ancien algorithme aux paires restantes.

Vous pouvez trouver des lignes de longueur infinie (pseudo-aléatoire) en calculant la normale au milieu de la ligne reliant les centres de deux polygones dans votre ensemble de polygones.