Ich brauche eine Grundfunktion, um den kürzesten Abstand zwischen einem Punkt und einem Liniensegment zu finden. Sie können die Lösung auch in einer beliebigen Sprache schreiben. Ich kann es in das übersetzen, was ich benutze (Javascript).
BEARBEITEN: Mein Liniensegment wird durch zwei Endpunkte definiert. Mein Liniensegment AB
wird also durch die beiden Punkte A (x1,y1)
und definiert B (x2,y2)
. Ich versuche, den Abstand zwischen diesem Liniensegment und einem Punkt zu ermitteln C (x3,y3)
. Meine Geometriekenntnisse sind verrostet, daher sind die Beispiele, die ich gesehen habe, verwirrend. Es tut mir leid, das zuzugeben.
language-agnostic
geometry
distance
line-segment
Eli Courtwright
quelle
quelle
Antworten:
Eli, der Code, auf den du dich festgelegt hast, ist falsch. Ein Punkt in der Nähe der Linie, auf der das Segment liegt, aber weit entfernt von einem Ende des Segments, würde in der Nähe des Segments falsch beurteilt.Update: Die angegebene falsche Antwort ist nicht mehr die akzeptierte.Hier ist ein korrekter Code in C ++. Es
class vec2 {float x,y;}
wird im Wesentlichen ein Klasse-2D-Vektor mit Operatoren zum Addieren, Subtrahieren, Skalieren usw. sowie einer Distanz- und Punktproduktfunktion (dhx1 x2 + y1 y2
) vorausgesetzt .EDIT: Ich brauchte eine Javascript-Implementierung, also hier ist es ohne Abhängigkeiten (oder Kommentare, aber es ist ein direkter Port der oben genannten). Punkte werden als Objekte mit
x
undy
Attributen dargestellt.EDIT 2: Ich brauchte eine Java-Version, aber was noch wichtiger ist, ich brauchte sie in 3D statt in 2D.
quelle
p
auf eine Linie ist der Punkt auf der Linie, der am nächsten liegtp
. (Und ein senkrecht zu der Linie auf der Projektion wird durchlaufenp
.) Die Anzahlt
ist , wie weit entlang des Liniensegmentes ausv
zu ,w
dass die Projektion fällt. Wennt
also 0 ist, fällt die Projektion genau aufv
; wenn es 1 ist, ist es anw
; Wenn es zum Beispiel 0,5 ist, liegt es auf halbem Weg dazwischen. Wennt
es kleiner als 0 oder größer als 1 ist, fällt es auf die Linie hinter dem einen oder anderen Ende des Segments. In diesem Fall ist der Abstand zum Segment der Abstand zum näheren Ende.Hier ist der einfachste vollständige Code in Javascript.
x, y ist dein Zielpunkt und x1, y1 bis x2, y2 ist dein Liniensegment.
AKTUALISIERT: Behebung eines Zeilenproblems mit 0 Längen aus Kommentaren.
quelle
Dies ist eine Implementierung, die für FINITE LINE SEGMENTS erstellt wurde, nicht für unendliche Zeilen, wie es die meisten anderen Funktionen hier zu sein scheinen (deshalb habe ich dies gemacht).
Umsetzung der Theorie von Paul Bourke .
Python:
AS3:
Java
quelle
distAnother(0, 0, 4, 0, 2, 2)
ergibt 2.8284271247461903 (falsch).distAnother(0., 0., 4., 0., 2., 2.)
ergibt 2,0 (richtig). Bitte beachten Sie dies. Ich denke, der Code kann verbessert werden, um irgendwo eine Float-Konvertierung zu haben.In meinem eigenen Fragenthread, wie man den kürzesten 2D-Abstand zwischen einem Punkt und einem Liniensegment in allen Fällen in C, C # / .NET 2.0 oder Java berechnet? Ich wurde gebeten, hier eine C # -Antwort einzugeben, wenn ich eine finde: Hier ist sie, geändert von http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :
Ich bin @SO, um nicht zu antworten, sondern Fragen zu stellen, also hoffe ich, dass ich aus bestimmten Gründen keine Millionen Stimmen bekomme, sondern Kritiker konstruiere. Ich wollte (und wurde ermutigt) nur die Ideen eines anderen teilen, da die Lösungen in diesem Thread entweder in einer exotischen Sprache (Fortran, Mathematica) vorliegen oder von jemandem als fehlerhaft markiert wurden. Das einzig nützliche (von Grumdrig) für mich ist mit C ++ geschrieben und niemand hat es als fehlerhaft markiert. Es fehlen jedoch die aufgerufenen Methoden (Punkt usw.).
quelle
In F # ist der Abstand vom Punkt
c
zum Liniensegment zwischena
undb
gegeben durch:Der Vektor
d
zeigt vona
bisb
entlang des Liniensegments. Das Punktprodukt vond/s
mitc-a
gibt den Parameter des Punktes der nächsten Annäherung zwischen der unendlichen Linie und dem Punkt anc
. Diemin
undmax
-Funktion wird verwendet, um diesen Parameter auf den Bereich zu klemmen,0..s
sodass der Punkt zwischena
und liegtb
. Schließlich ist die Länge vona+p-c
der Abstand vomc
nächsten Punkt auf dem Liniensegment.Anwendungsbeispiel:
quelle
(a + p - c).Length
lambda
bzw.p
alslet lambda = (c - a) * d / (s * s)
und neu zu definierenlet p = a + (lambda |> max 0.0 |> min 1.0) * d
. Danach gibt die Funktion den korrekten Abstand zurück, z. B. für den Falla = (0,1)
, in demb = (1,0)
undc = (1,1)
.Für alle Interessierten gibt es hier eine triviale Konvertierung von Joshuas Javascript-Code in Objective-C:
Ich brauchte diese Lösung, um
MKMapPoint
damit arbeiten zu können, damit ich sie weitergeben kann, falls jemand anderes sie benötigt. Nur eine kleine Änderung und dies gibt die Entfernung in Metern zurück:quelle
In Mathematica
Es verwendet eine parametrische Beschreibung des Segments und projiziert den Punkt in die durch das Segment definierte Linie. Wenn der Parameter im Segment von 0 auf 1 geht und die Projektion außerhalb dieser Grenzen liegt, berechnen wir den Abstand zum entsprechenden Punkt anstelle der geraden Linie senkrecht zum Segment.
Darstellungsergebnis:
Zeichnen Sie diese Punkte näher als einen Grenzabstand :
Konturdiagramm:
quelle
Hey, das habe ich gestern gerade geschrieben. Es befindet sich in Actionscript 3.0, das im Grunde Javascript ist, obwohl Sie möglicherweise nicht dieselbe Point-Klasse haben.
Außerdem gibt es hier eine ziemlich vollständige und lesbare Diskussion des Problems: notejot.com
quelle
Für die Faulen ist hier mein Objective-C-Port von @ Grumdrigs Lösung oben:
quelle
return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
sqrtf(x) = x*x
.Konnte nicht widerstehen, es in Python zu codieren :)
Das Gleiche gilt für fortran :)
quelle
Hier ist eine vollständigere Schreibweise aus Grumdrigs Lösung. Diese Version gibt auch den nächstgelegenen Punkt selbst zurück.
quelle
Einzeilige Lösung mit Arkustangens:
Die Idee ist, A nach (0, 0) zu bewegen und das Dreieck im Uhrzeigersinn zu drehen, damit C auf der X-Achse liegt. In diesem Fall ist By der Abstand.
C #
Eine Zeile C # (zur Konvertierung in SQL)
quelle
Betrachten Sie diese Änderung der obigen Antwort von Grumdrig. Oft werden Sie feststellen, dass Gleitkomma-Ungenauigkeiten Probleme verursachen können. Ich verwende in der folgenden Version Doppel, aber Sie können leicht zu Floats wechseln. Der wichtige Teil ist, dass es ein Epsilon verwendet, um den "Slop" zu handhaben. Außerdem möchten Sie oft wissen, wo die Kreuzung passiert ist oder ob sie überhaupt passiert ist. Wenn das zurückgegebene t <0,0 oder> 1,0 ist, ist keine Kollision aufgetreten. Selbst wenn keine Kollision aufgetreten ist, möchten Sie oft wissen, wo der Punkt auf dem Segment am nächsten zu P liegt, und daher verwende ich qx und qy, um diesen Ort zurückzugeben.
quelle
Ich gehe davon aus, dass Sie den kürzesten finden möchtenAbstand zwischen dem Punkt und einem Liniensegment; Dazu müssen Sie die Linie (Linie A) finden, die senkrecht zu Ihrem Liniensegment (Linie B) verläuft, das durch Ihren Punkt verläuft. Bestimmen Sie den Schnittpunkt zwischen dieser Linie (Linie A) und Ihrer Linie, die durch Ihr Liniensegment verläuft (Linie B). ;; Wenn dieser Punkt zwischen den beiden Punkten Ihres Liniensegments liegt, ist der Abstand der Abstand zwischen Ihrem Punkt und dem Punkt, den Sie gerade gefunden haben und der Schnittpunkt von Linie A und Linie B ist. Wenn der Punkt nicht zwischen den beiden Punkten Ihres Liniensegments liegt, müssen Sie den Abstand zwischen Ihrem Punkt und dem näheren von zwei Enden des Liniensegments ermitteln. Dies kann leicht erreicht werden, indem der Quadratabstand (um eine Quadratwurzel zu vermeiden) zwischen dem Punkt und den beiden Punkten des Liniensegments genommen wird. was auch immer näher ist, nimm die Quadratwurzel von diesem.
quelle
Die C ++ / JavaScript-Implementierung von Grumdrig war für mich sehr nützlich, daher habe ich einen Python-Direktport bereitgestellt, den ich verwende. Der vollständige Code ist hier .
quelle
Matlab-Code mit integriertem "Selbsttest", wenn die Funktion ohne Argumente aufgerufen wird:
quelle
Und jetzt auch meine Lösung ...... (Javascript)
Es ist sehr schnell, weil ich versuche, Math.pow-Funktionen zu vermeiden.
Wie Sie sehen können, habe ich am Ende der Funktion den Abstand der Linie.
Der Code stammt aus der Bibliothek http://www.draw2d.org/graphiti/jsdoc/#!/example
quelle
codiert in t-sql
Der Punkt ist (@px, @py) und das Liniensegment verläuft von (@ax, @ay) nach (@bx, @by).
quelle
Es sieht so aus, als hätten fast alle anderen auf StackOverflow eine Antwort beigesteuert (bisher 23 Antworten). Hier ist mein Beitrag für C #. Dies basiert hauptsächlich auf der Antwort von M. Katz, die wiederum auf der Antwort von Grumdrig basiert.
Und hier ist ein kleines Testprogramm.
Wie Sie sehen können, habe ich versucht, den Unterschied zwischen der Verwendung der Version, die die Sqrt () -Methode vermeidet, und der normalen Version zu messen. Meine Tests zeigen, dass Sie vielleicht etwa 2,5% sparen können, aber ich bin mir nicht einmal sicher - die Abweichungen innerhalb der verschiedenen Testläufe waren in der gleichen Größenordnung. Ich habe auch versucht, die von Matti veröffentlichte Version zu messen (plus eine offensichtliche Optimierung), und diese Version scheint etwa 4% langsamer zu sein als die auf Katz / Grumdrig-Code basierende Version.
Bearbeiten: Übrigens habe ich auch versucht, eine Methode zu messen, die den Abstand zu einer unendlichen Linie (kein Liniensegment) mit einem Kreuzprodukt (und einem Sqrt ()) ermittelt, und sie ist ungefähr 32% schneller.
quelle
Hier ist die C ++ - Version von devnullicus, die in C # konvertiert wurde. Für meine Implementierung musste ich den Schnittpunkt kennen und fand, dass seine Lösung gut funktioniert.
quelle
Hier wird Swift verwendet
quelle
C #
Adaptiert von @Grumdrig
quelle
Eine 2D- und 3D-Lösung
Betrachten Sie eine Änderung der Basis, so dass das Liniensegment
(0, 0, 0)-(d, 0, 0)
und der Punkt wird(u, v, 0)
. Die kürzeste Entfernung tritt in dieser Ebene auf und ist gegeben durch(Der Abstand zu einem der Endpunkte oder zur Stützlinie hängt von der Projektion auf die Linie ab. Der Iso-Distanz-Ort besteht aus zwei Halbkreisen und zwei Liniensegmenten.)
In dem obigen Ausdruck ist d die Länge des Segments AB und u, v sind jeweils das Skalarprodukt und (Modul des) Kreuzprodukts von AB / d (Einheitsvektor in Richtung AB) und AC. Daher vektoriell
quelle
Weitere Informationen finden Sie in der Matlab GEOMETRY-Toolbox auf der folgenden Website: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html
Strg + f und geben Sie "segment" ein, um liniensegmentbezogene Funktionen zu finden. Die Funktionen "segment_point_dist_2d.m" und "segment_point_dist_3d.m" sind genau das, was Sie brauchen.
Die GEOMETRY-Codes sind in einer C-Version und einer C ++ - Version sowie einer FORTRAN77-Version und einer FORTRAN90-Version und einer MATLAB-Version verfügbar.
quelle
AutoHotkeys-Version basierend auf Joshuas Javascript:
quelle
Da hier keine Java-Implementierung angezeigt wurde, habe ich die Javascript-Funktion aus der akzeptierten Antwort in Java-Code übersetzt:
quelle
WPF-Version:
quelle
Hier ist der Code, den ich am Ende geschrieben habe. Dieser Code setzt voraus, dass ein Punkt in Form von definiert ist
{x:5, y:7}
. Beachten Sie, dass dies nicht der absolut effizienteste Weg ist, aber es ist der einfachste und am einfachsten zu verstehende Code, den ich finden könnte.quelle
Die obige Funktion funktioniert nicht bei vertikalen Linien. Hier ist eine Funktion, die gut funktioniert! Linie mit den Punkten p1, p2. und CheckPoint ist p;
quelle
Hier ist das Gleiche wie bei der C ++ - Antwort, jedoch auf Pascal portiert. Die Reihenfolge des Punktparameters hat sich geändert, um meinem Code zu entsprechen, ist aber dasselbe.
quelle