Kürzeste Entfernung zwischen zwei Liniensegmenten
Ich brauche eine Funktion zu finden, die kürzeste Entfernung zwischen zwei Liniensegmenten. Ein Liniensegment wird durch zwei definierten Endpunkten. So zum Beispiel einer meiner Liniensegmente (AB) wäre definiert durch die zwei Punkte A (x1,y1) und B (x2,y2) und die andere (CD) definiert durch die beiden Punkte C (x1,y1) und D (x2,y2).
Fühlen Sie sich frei, zu schreiben, die Lösung in jeder Sprache, die Sie wollen, und kann ich es übersetzen in javascript. Bitte beachten Sie meine geometrie-Kenntnisse sind ziemlich eingerostet. Ich habe schon gesehen, hier und ich bin nicht sicher, wie Sie Sie übersetzen diese in eine Funktion. Vielen Dank für die Hilfe.
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ist diese in 2 Dimensionen? Wenn dem so ist, die Antwort ist einfach, die kürzeste Entfernung zwischen Punkt A und Liniensegment CD -, B-und CD -, C-und AB-oder D und AB. Also es ist ein ziemlich einfaches "Abstand zwischen Punkt und Linie" Berechnung (wenn die Abstände sind alle gleich, dann sind die geraden parallel sind).
Diese Seite erklärt den Algorithmus für den Abstand zwischen einem Punkt und einer Linie, ziemlich gut.
Ist es etwas tricky, die in den 3 Dimensionen, da die Linien nicht unbedingt in der gleichen Ebene, aber das scheint nicht der Fall zu sein?
u
auf den Bereich [0,1]).Dies ist meine Lösung in python. Arbeitet mit der 3d-Punkte und können Sie zur Vereinfachung für 2d.
[EDIT 1] ich habe eine clamp option, wenn Sie möchten, um die Ergebnisse einzuschränken, um die Liniensegmente
[EDIT 2] B. D. A. darauf hingewiesen, weil zwei geraden parallel sind, bedeutet nicht, Sie können keine Entfernung zwischen Ihnen. Also bearbeitete ich den code zur Verarbeitung dieser situation. Ich habe auch den clamp-Bedingungen noch allgemeiner, so dass die einzelnen Segmente eingespannt werden kann, auf beiden Seiten.
[EDIT 3] Adressiert einen Fehler jhutar wies darauf hin, die auftreten könnten, wenn beide Linien haben geklemmt Bedingungen und die prognostizierten Ergebnisse gehen über die Liniensegmente.
Test-Beispiel mit Bildern zu visualisieren 🙂
Entnommen dieses Beispiel, die kommt auch mit einer einfachen Erklärung, warum es funktioniert so gut wie VB-code (das ist mehr, als Sie brauchen, so habe ich vereinfacht, da ich übersetzt Python -- Anmerkung: ich habe übersetzt, aber nicht getestet, also ein Tippfehler vielleicht entgangen...):
Die Entfernung zwischen den Linien und Segmente
mit Ihrer dichtesten Annäherung
Für die Berechnung der Mindest-Abstand zwischen 2 2D-Linien-Segmenten ist es wahr, dass Sie eine 4 senkrechten Abstand von Endpunkt zu anderen line-Prüfungen nacheinander mit jedem der 4 Endpunkte. Allerdings, wenn Sie feststellen, dass die senkrechte Linie gezogen überschneidet sich nicht mit dem line-segment in jedem der 4 Fälle, dann musst du die 4 zusätzlichen Endpunkt-zu-Endpunkt-distance-Prüfungen finden Sie den kürzesten Abstand.
Ob es eine elegante Lösung weiß ich auch nicht.
Bitte beachten Sie, dass die oben genannten Lösungen sind korrekt unter der Annahme, dass die Liniensegmente nicht schneiden! Wenn die Liniensegmente sich schneiden, ist es klar, dass Ihre Entfernung sollte 0 sein. Es ist daher notwendig, um eine abschließende Prüfung, das ist: Angenommen, der Abstand zwischen Punkt A und CD, d(A,CD), war der kleinste der 4 Prüfungen genannt, die von Dean. Dann nehmen Sie einen kleinen Schritt entlang der Strecke AB, um von Punkt A. wir Bezeichnen diesen Punkt Z, Wenn d(E,CD) < d(A,CD), die Segmente müssen sich überschneidenden! Beachten Sie, dass dies nie der Fall sein gerichtet durch Stephen.
Meine Lösung ist eine übersetzung des Fnord-Lösung. Ich mache in javascript und C.
In Javascript. Sie müssen mathjs.
In reinem C
Diese Lösung ist im wesentlichen der von Alex Martelli, aber ich habe ein Punkt-und ein LineSegment-Klasse, um das Lesen zu erleichtern. Ich habe auch die Formatierung angepasst und Hinzugefügt einige tests.
The line segment intersection falsch ist, aber es scheint nicht zu Rolle, für die Berechnung der Entfernung von Linien-Segmenten. Wenn Sie interessiert sind, in einem richtigen line-segment-intersection derst, schau mal hier: Wie Sie erkennen, ob zwei Liniensegmente sich schneiden?
Ich habe einen Swift-Anschluss basiert auf Pratik Deoghare die Antwort von oben. Pratik Referenzen Dan Sonntag, hervorragende schreib-und code-Beispiele finden Sie hier: http://geomalgorithms.com/a07-_distance.html
Folgende Funktionen berechnen Sie die minimale Distanz zwischen zwei Linien oder zwei Liniensegmente, und ist ein direkter port von Dan am Sonntag die C++ - Beispiele.
Den LASwift lineare algebra-Paket wird verwendet, um zu tun, die matrix-und Vektor-Berechnungen.