Comment détecter les collisions 2D en ligne?

13

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

pas d'intersection pas d'intersection intersection pas d'intersection

PS J'essaye de faire une fonction

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

Merci d'avance.

Vishnu
la source
6
C'est une explication décevante et non visuelle du problème, mais c'est un algorithme et cela a du sens si vous pouvez vous résoudre à lire leurs maths: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d Cela peut être lourd si vos calculs vectoriels sont faibles. Je comprends - je préfère également les explications visuelles. J'essaierai de trouver du temps plus tard pour gribouiller cela, mais si quelqu'un du tout artistiquement incliné voit ce lien et a le temps avant moi, allez-y!
Anko

Réponses:

18

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:

entrez la description de l'image ici

David Gouveia
la source
Je n'ai pas obtenu de résultat de cet algorithme, désolé!
Vishnu
4
@Vish Quel problème avez-vous rencontré? J'ai testé cette copie exacte de l'algorithme avant de poster et cela a fonctionné parfaitement, sauf pour le cas unique décrit.
David Gouveia
Ensuite, laissez-moi réessayer, j'aurais peut-être mélangé des mathématiques. Je te le ferai bientôt savoir. Merci beaucoup, nyways :)
Vishnu
1
J'ai obtenu le résultat souhaité de votre algorithme, merci @DavidGouveia.
Vishnu
1
Eh bien, mais maintenant j'ai un autre problème :)! J'ai besoin de faire les lignes intersectées avec la couleur rouge et le vert. L'intersection fonctionne bien. Mais comme je l'ai compris maintenant (pas mathématiquement cependant) qu'un simple if-else ne fonctionnera pas comme pour mettre des lignes rouges et vertes pour les lignes intersectées et non intersectées. Le nœud que je fais glisser a à la fois une ligne gauche et une ligne droite. Donc, quelque chose s'est mal passé quelque part en changeant la couleur des lignes non coupées en vert. Je suppose que j'ai aussi besoin d'une autre condition. Hmmm, de toute façon merci une tonne, je marque cela comme la bonne réponse.
Vishnu
4

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.

Valmond
la source
1
Je suis désolé mais je ne suis pas assez bon en mathématiques vectorielles, j'ai implémenté cet algorithme en tant que tel, mais je n'ai obtenu aucun résultat, désolé!
Vishnu
1
Cela devrait fonctionner alors peut-être que si vous pouvez nous montrer votre code, nous pouvons vous aider là-bas?
Valmond
Agréable! mais le lien est rompu
clabe45
Pouvez-vous ajouter quelque chose pour obtenir le point d'intersection?
SeanRamey
1

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));
Lukáš Čulen
la source
Je pense que cette réponse pourrait vraiment s'améliorer si vous expliquiez ce que fait le code.
TomTsagk
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)

Jorammer
la source
Existe-t-il une version de ceci qui renvoie le point d'intersection?
SeanRamey