Wie erkennt man 2D-Linien bei Linienkollisionen?

13

Ich bin ein Flash-Actionscript-Spieleentwickler, der mit Mathematik ein bisschen rückständig ist, obwohl ich Physik sowohl interessant als auch cool finde.

Als Referenz ist dies ein ähnliches Spiel wie das, das ich mache: Unangled Flash-Spiel

Ich habe dieses entwirrte Spiel fast zur vollständigen Vervollständigung der Logik gemacht. Wenn sich zwei Linien kreuzen, brauche ich diese gekreuzten oder verworrenen Linien, um eine andere Farbe zu zeigen. rot.

Es wäre wirklich nett von Ihnen, wenn Sie einen Algorithmus zur Erkennung von Liniensegmentkollisionen vorschlagen könnten . Ich bin im Grunde eine Person, die lieber 'visuell' als 'arithmetisch' denkt :)

Bearbeiten: Ich möchte ein paar Diagramme hinzufügen, um die Idee klarer zu vermitteln

keine Kreuzung keine Kreuzung Überschneidung keine Kreuzung

PS Ich versuche eine Funktion als zu machen

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

Danke im Voraus.

Vishnu
quelle
6
Dies ist eine enttäuschend nicht visuelle Erklärung des Problems, aber es ist ein Algorithmus und es ist sinnvoll, wenn Sie sich dazu bringen können, ihre Mathematik zu lesen: local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d Es kann sein Seien Sie schwer, wenn Ihre Vektor-Mathematik schwach ist. Ich verstehe - ich bevorzuge auch visuelle Erklärungen. Ich werde versuchen, später Zeit zu finden, um dies zu kritzeln, aber wenn jemand, der überhaupt künstlerisch veranlagt ist, diesen Link sieht und Zeit hat, bevor ich es tue, komme ich dazu!
Anko

Antworten:

18

Ich verwende die folgende Methode, die so ziemlich nur eine Implementierung dieses Algorithmus ist . Es ist in C #, aber die Übersetzung in ActionScript sollte trivial sein.

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);
}

Es gibt jedoch ein subtiles Problem mit dem Algorithmus. In diesem Fall stimmen zwei Zeilen überein, überlappen sich jedoch nicht. Der Algorithmus gibt in diesem Fall immer noch eine Schnittmenge zurück. Wenn Sie sich für diesen Fall interessieren, glaube ich, dass diese Antwort auf stackoverflow eine komplexere Version hat, die sich damit befasst.

Bearbeiten

Ich habe von diesem Algorithmus kein Ergebnis erhalten, sorry!

Das ist seltsam, ich habe es getestet und es funktioniert für mich mit Ausnahme des oben beschriebenen Einzelfalls. Mit genau der gleichen Version, die ich oben gepostet habe, habe ich die folgenden Ergebnisse erhalten, als ich es für eine Probefahrt gemacht habe:

Bildbeschreibung hier eingeben

David Gouveia
quelle
Ich habe von diesem Algorithmus kein Ergebnis erhalten, sorry!
Vishnu
4
@Vish Welches Problem hattest du? Ich habe diese exakte Kopie des Algorithmus vor dem Posten getestet und sie hat einwandfrei funktioniert, mit Ausnahme des beschriebenen Einzelfalls.
David Gouveia
Dann lassen Sie es mich noch einmal versuchen, ich hätte vielleicht etwas Mathe hineingemischt. Ich werde es dich bald wissen lassen. Vielen Dank, nyways :)
Vishnu
1
Ich habe das gewünschte Ergebnis von Ihrem Algorithmus erhalten, danke @DavidGouveia.
Vishnu
1
Naja, aber jetzt habe ich noch ein Problem :)! Ich muss die geschnittenen Linien mit roter Farbe und grün machen. Die Kreuzung funktioniert gut. Aber wie ich jetzt verstanden habe (nicht mathematisch gesehen), funktioniert ein einfaches Wenn-Sonst nicht wie das Setzen von roten und grünen Linien für geschnittene und nicht geschnittene Linien. Der Knoten, den ich ziehe, hat eine linke und eine rechte Linie. Irgendwo ist also etwas schief gegangen, als die Farbe der nicht geschnittenen Linien wieder in Grün geändert wurde. Ich denke, ich brauche auch eine andere Bedingung. Hmmm, trotzdem vielen Dank, ich markiere dies als die richtige Antwort.
Vishnu
4

Ohne Abteilungen! Also kein Problem mit Präzision oder Division durch Null.

Liniensegment 1 ist A nach B Liniensegment 2 ist C nach D

Eine Linie ist eine nie endende Linie, das Liniensegment ist ein definierter Teil dieser Linie.

Überprüfen Sie, ob sich die beiden Begrenzungsrahmen überschneiden: Wenn keine Überschneidung -> Kein Kreuz! (Berechnung abgeschlossen, Rückgabe falsch)

Überprüfen Sie, ob die Linie seg 1 die Linie seg 2 überspannt und ob die Linie seg 2 die Linie seg 1 überspannt (dh das Liniensegment 1 befindet sich auf beiden Seiten der Linie, die durch das Liniensegment 2 definiert ist).

Dies kann erreicht werden, indem alle Punkte mit -A übersetzt werden (dh Sie verschieben die 2 Linien so, dass A in Origo ist (0,0)).

Dann prüfen Sie, ob sich die Punkte C und D auf verschiedenen Seiten der durch 0,0 bis B definierten Linie befinden

//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!

Wenn Sie noch kein "Kein Kreuz" haben, verwenden Sie weiterhin nicht A, B gegen C, D, sondern C, D gegen A, B (gleiche Berechnungen, tauschen Sie einfach A und C, B und D aus), wenn es keine gibt "Kein Kreuz!" dann hast du eine kreuzung!

Ich suchte nach den genauen Berechnungen für das Kreuzprodukt und fand diesen Blogeintrag , der auch die Methode erklärt.

Valmond
quelle
1
Es tut mir leid, aber ich kann nicht ganz gut mit Vektor-Mathematik umgehen. Ich habe diesen Algorithmus als solchen implementiert, aber leider kein Ergebnis erzielt.
Vishnu
1
Es sollte also funktionieren, wenn Sie uns Ihren Code zeigen können, können wir Ihnen da draußen helfen?
Valmond
Nett! Die Verbindung ist jedoch unterbrochen
clabe45
Gibt es etwas, das Sie hinzufügen können, um den Schnittpunkt zu ermitteln?
SeanRamey
1

Ich möchte nur sagen, ich brauchte es für mein Gamemaker Studio-Spiel und es funktioniert gut:

///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
quelle
Ich denke, diese Antwort könnte sich wirklich verbessern, wenn Sie erklären, was der Code bewirkt.
TomTsagk
1

Die akzeptierte Antwort ergab in diesem Fall eine falsche Antwort:

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

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

Diese Linien kreuzen sich offensichtlich nicht, aber entsprechend der Funktion in der "richtigen Antwort" kreuzen sich die Linien.

Das benutze ich:

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;
}

gibt 0 zurück = die Linien schneiden sich nicht

gibt> 0 zurück = die Linien schneiden sich


Aktualisieren Sie, um die Frage zu beantworten:

Ich habe diesen Code nicht selbst erstellt. Es ist über 5 Jahre alt und ich weiß nicht, was die ursprüngliche Quelle ist. Aber..

Ich denke, der Rückgabewert ist die relative Position der ersten Zeile, in der sie sich kreuzen (um es schlecht zu erklären). Um den Schnittpunkt zu berechnen, könnten Sie wahrscheinlich lerp wie folgt verwenden:

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

(Ich habe das nicht getestet)

Jorammer
quelle
Gibt es eine Version davon, die den Schnittpunkt zurückgibt?
SeanRamey