Comment détecter les collisions 2D en ligne?

Je suis un développeur de jeux flash actionscript qui est un peu en arrière avec les mathématiques, bien que je trouve la physique à la fois intéressante et cool.

Pour référence, c'est un jeu similaire à celui que je fais: jeu flash Untangled

J'ai fait de ce jeu démêlé presque complètement la logique. Mais, lorsque deux lignes se croisent, j'ai besoin de ces lignes croisées ou «emmêlées» pour montrer une couleur différente; rouge.

Ce serait vraiment gentil de votre part si vous pouviez suggérer un algorithme pour détecter les collisions de segments de ligne . Je suis fondamentalement une personne qui aime penser «visuellement» qu'arithmétiquement :)

Edit: je voudrais ajouter quelques diagrammes pour faire passer l'idée plus clairement

PS J'essaye de faire une fonction

private function isIntersecting(A:Point, B:Point, C:Point, D:Point):Boolean

Merci d'avance.

J'utilise la méthode suivante qui est à peu près juste une implémentation de cet algorithme . Il est en C # mais sa traduction en ActionScript devrait être triviale.

bool IsIntersecting(Point a, Point b, Point c, Point d)
{
    float denominator = ((b.X - a.X) * (d.Y - c.Y)) - ((b.Y - a.Y) * (d.X - c.X));
    float numerator1 = ((a.Y - c.Y) * (d.X - c.X)) - ((a.X - c.X) * (d.Y - c.Y));
    float numerator2 = ((a.Y - c.Y) * (b.X - a.X)) - ((a.X - c.X) * (b.Y - a.Y));

    // Detect coincident lines (has a problem, read below)
    if (denominator == 0) return numerator1 == 0 && numerator2 == 0;

    float r = numerator1 / denominator;
    float s = numerator2 / denominator;

    return (r >= 0 && r <= 1) && (s >= 0 && s <= 1);
}

Il y a cependant un problème subtil avec l'algorithme, ce qui est le cas dans lequel deux lignes coïncident mais ne se chevauchent pas. L'algorithme renvoie toujours une intersectioin dans ce cas. Si vous vous souciez de ce cas, je crois que cette réponse sur stackoverflow a une version plus complexe qui y répond.

Éditer

Je n'ai pas obtenu de résultat de cet algorithme, désolé!

C'est étrange, je l'ai testé et cela fonctionne pour moi, sauf pour le cas unique que j'ai décrit ci-dessus. En utilisant exactement la même version que j'ai publiée ci-dessus, j'ai obtenu ces résultats lorsque je l'ai pris pour un essai routier:

Sans divisions! Donc pas de problème de précision ni de division par zéro.

Le segment de ligne 1 est de A à B Le segment de ligne 2 est de C à D

Une ligne est une ligne sans fin, le segment de ligne est une partie définie de cette ligne.

Vérifiez si les deux boîtes englobantes se croisent: si aucune intersection -> Pas de croix! (calcul effectué, retour faux)

Vérifiez si la ligne seg 1 chevauche la ligne seg 2 et si la ligne seg 2 chevauche la ligne seg 1 (c'est-à-dire que le segment de ligne 1 est des deux côtés de la ligne définie par la ligne segment 2).

Cela peut être fait en traduisant tous les points par -A (c'est-à-dire que vous déplacez les 2 lignes pour que A soit en origo (0,0))

Ensuite, vous vérifiez si les points C et D sont de différents côtés de la ligne définie par 0,0 à B

//Cross Product (hope I got it right here)
float fC= (B.x*C.y) - (B.y*C.x); //<0 == to the left, >0 == to the right
float fD= (B.x*D.y) - (B.y*D.x);

if( (fc<0) && (fd<0)) //both to the left  -> No Cross!
if( (fc>0) && (fd>0)) //both to the right -> No Cross!

Si vous n'avez pas encore obtenu "Pas de croix", continuez à utiliser non pas A, B contre C, D mais C, D contre A, B (mêmes calculs, échangez simplement A et C, B et D), s'il n'y a pas "Pas de croix!" alors vous avez une intersection!

J'ai cherché les calculs exacts pour le produit croisé et j'ai trouvé cet article de blog qui explique également la méthode.

Je veux juste dire que j'en avais besoin pour mon jeu Gamemaker Studio et cela fonctionne bien:

///scr_line_collision(x1,y1,x2,y2,x3,y3,x4,y4)

var denominator= ((argument2 - argument0) * (argument7 - argument5)) - ((argument3 - argument1) * (argument6 - argument4));
var numerator1 = ((argument1 - argument5) * (argument6 - argument4)) - ((argument0 - argument4) * (argument7 - argument5));
var numerator2 = ((argument1 - argument5) * (argument2 - argument0)) - ((argument0 - argument4) * (argument3 - argument1));

// Detect coincident lines
if (denominator == 0) {return (numerator1 == 0 && numerator2 == 0)}

var r = numerator1 / denominator;
var s = numerator2 / denominator;

return ((r >= 0 && r <= 1) && (s >= 0 && s <= 1));

La réponse acceptée a donné une mauvaise réponse dans ce cas:

x1 = 0;
y1 = 0;
x2 = 10;
y2 = 10;

x3 = 10.1;
y3 = 10.1;
x4 = 15;
y4 = 15;

Ces lignes ne se coupent évidemment pas, mais selon la fonction de la "bonne réponse", les lignes se croisent.

Voici ce que j'utilise:

function do_lines_intersect(px1,py1,px2,py2,px3,py3,px4,py4) {
  var ua = 0.0;
  var ub = 0.0;
  var ud = (py4 - py3) * (px2 - px1) - (px4 - px3) * (py2 - py1);


  if (ud != 0) {
    ua = ((px4 - px3) * (py1 - py3) - (py4 - py3) * (px1 - px3)) / ud;
    ub = ((px2 - px1) * (py1 - py3) - (py2 - py1) * (px1 - px3)) / ud;
        if (ua < 0.0 || ua > 1.0 || ub < 0.0 || ub > 1.0) ua = 0.0;
  }

  return ua;
}

renvoie 0 = les lignes ne se coupent pas

renvoie> 0 = les lignes se croisent

Mettre à jour pour répondre à la question:

Je n'ai pas créé ce code moi-même. Il a plus de 5 ans et je ne connais pas la source d'origine. Mais..

Je pense que la valeur de retour est la position relative de la première ligne où ils se croisent (pour l'expliquer mal). Pour calculer le point d'intersection, vous pourriez probablement utiliser lerp comme ceci:

l = do_lines_intersect(...)
if (l > 0) {
    intersect_pos_x = l * (px2-px1);
    intersect_pos_y = l * (py2-py1);
} else {
    // lines do not cross
}

(JE N'AI PAS TESTÉ CELA)