Verbinde zwei Liniensegmente

Unter Verwendung der allgemeinen Idee Afterlife und Rob Parkers Algorithmen oben, hier ist eine C ++ - Version einer Reihe von Methoden, um den Mindestabstand zwischen 2 beliebigen 2D-Segmenten zu erhalten. Dies behandelt überlappende Segmente, parallele Segmente, sich überschneidende und nicht überschneidende Segmente. Darüber hinaus werden verschiedene Epsilon-Werte verwendet, um die Ungenauigkeit der Gleitkommazahl zu verhindern. Schließlich gibt Ihnen dieser Algorithmus zusätzlich zum Zurückgeben des Mindestabstandes den Punkt in Segment 1, der dem Segment 2 am nächsten liegt (der auch der Schnittpunkt ist, wenn sich die Segmente schneiden). Es wäre ziemlich trivial, auch den Punkt auf [p3, p4] möglichst nahe bei [p1, p2] zurückzugeben, aber ich überlasse das dem Leser als Übung:)

Schneller Tipp: Wenn Sie Entfernungen anhand von Punkten vergleichen möchten, ist es nicht notwendig, die Quadratwurzeln zu verwenden.

z. um zu sehen, ob P-zu-Q eine kleinere Entfernung als Q-zu-R ist, überprüfen Sie einfach (Pseudocode):

Afterlife sagt: "Überprüfen Sie zuerst, ob sich die beiden Linien mit diesem Algorithmus schneiden", aber er hat nicht angegeben, welchen Algorithmus er meinte. Offensichtlich ist es der Schnittpunkt der Linie Segmente nicht die erweiterten Linien, was zählt; Alle nichtparallelen Liniensegmente (ausgenommen koinzidente Endpunkte, die keine Linie definieren) schneiden sich, aber der Abstand zwischen den Liniensegmenten ist nicht notwendigerweise Null. Ich nehme an, er meinte dort eher "Liniensegmente" als "Linien".

Der Link Afterlife gab einen sehr eleganten Ansatz, um den nächsten Punkt auf einer Linie (oder einem Liniensegment oder einem Strahl) zu einem anderen beliebigen Punkt zu finden. Dies funktioniert, um die Entfernung von jedem Endpunkt zu dem anderen Liniensegment zu finden (Beschränken des berechneten Parameters u auf nicht weniger als 0 für ein Liniensegment oder Strahl und nicht mehr als 1 für ein Liniensegment), tut dies jedoch nicht Behandle die Möglichkeit, dass ein innerer Punkt auf einem Liniensegment näher als jeder Endpunkt ist, da sie sich tatsächlich schneiden, daher ist eine zusätzliche Überprüfung des Schnittpunkts erforderlich.

Was den Algorithmus zur Bestimmung der Liniensegmentüberschneidung anbelangt, wäre ein Ansatz, den Schnittpunkt der erweiterten Linien zu finden (wenn Sie dann parallel sind) und dann zu bestimmen, ob dieser Punkt innerhalb beider Liniensegmente liegt, wie z indem das Skalarprodukt der Vektoren vom Schnittpunkt T zu den zwei Endpunkten genommen wird:

((Tx - A1x) * (Tx - A2x)) + ((Ty - Aly) * (Ty - A2y))

Wenn dies negativ (oder "Null") ist, dann liegt T zwischen A1 und A2 (oder an einem Endpunkt). Überprüfen Sie ähnlich für das andere Liniensegment. Wenn beide größer als "Null" waren, schneiden sich die Liniensegmente nicht. Dies hängt natürlich davon ab, zuerst den Schnittpunkt der erweiterten Linien zu finden, was es erforderlich machen kann, jede Linie als eine Gleichung auszudrücken und das System durch Gauß-Reduktion (etc.) zu lösen.

Aber es kann einen direkteren Weg geben, ohne nach dem Schnittpunkt zu suchen, indem man das Kreuzprodukt der Vektoren (B1-A1) und (B2-A1) und das Kreuzprodukt der Vektoren (B1- A1) nimmt A2) und (B2-A2). Wenn diese Kreuzprodukte in der gleichen Richtung verlaufen, befinden sich A1 und A2 auf derselben Seite der Linie B; wenn sie in entgegengesetzte Richtungen sind, dann sind sie auf gegenüberliegenden Seiten der Linie B (und wenn 0, dann sind eins oder beide auf Linie B). In ähnlicher Weise die Kreuzprodukte der Vektoren (A1-B1) und (A2-B1) und (A1-B2) und (A2-B2) überprüfen. Wenn eines dieser Kreuzprodukte "Null" ist oder wenn die Endpunkte von beiden Liniensegmenten auf entgegengesetzte Seiten der anderen Linie fallen, müssen sich die Liniensegmente selbst schneiden, andernfalls schneiden sie sich nicht.

Natürlich brauchen Sie eine praktische Formel, um ein Kreuzprodukt zweier Vektoren aus ihren Koordinaten zu berechnen. Oder, wenn Sie die Winkel (positiv oder negativ) bestimmen könnten, würden Sie das tatsächliche Kreuzprodukt nicht benötigen, da es die Richtung der Winkel zwischen den Vektoren ist, die wir tatsächlich interessieren (oder der Sinus des Winkels wirklich) . Aber ich denke, die Formel für produktübergreifendes (in 2-D) ist einfach:

Kreuz (V1, V2) = (V1x * V2y) - (V2x * V1y)

Dies ist die z-Achsen-Komponente des 3D-Kreuzproduktvektors (wobei die x- und y-Komponenten Null sein müssen, da die Anfangsvektoren in der Ebene z = 0 liegen), so dass Sie einfach auf die Zeichen (oder "Null").

Sie können also eine der beiden Methoden verwenden, um im Algorithmus, den Afterlife beschreibt (Verweis auf die Verknüpfung), nach einer Liniensegment-Schnittmenge zu suchen.

Diese Seite hat eine schöne kurze Beschreibung, um den kürzesten Abstand zwischen zwei Zeilen zu finden, obwohl die @ strager-Verknüpfung einen Code enthält (in Fortran!)