Auf der Suche nach einem effizienten Algorithmus finden Sie die nächstgelegene Linie (definiert durch senkrechte Entfernung) an einen beliebigen Punkt

Question

Ich habe eine große Reihe von Linien in 2D mit einem bekannten Startpunkt und einem Endpunkt und möchte den nächstgelegenen (definierten durch senkrechten Abstand) dieser Kanten (oder die Erweiterung dieser Kanten an ihren Start- und Endpunkten an der Stelle vorbeifinden) zu einem willkürlichen Punkt.

Das Beste, was ich bisher getan habe, besteht darin, ein Satz von Beispielpunkten in jeder Zeile zu generieren und einen KD-Baum zu verwenden, um das nächstgelegene Nachbarproblem für die Punkte zu lösen - d. H. Finden Sie den nächstgelegenen Zeilenabtastpunkt auf den Abfragepunkt.Dies ist jedoch ungenau und braucht eine große Anzahl von Proben für lange Linien.

Ich habe das gesehen: Algorithmus für den nächsten RandErkennung in Bezug auf einen Punkt (in alle Richtungen)

aber er stützte sich auf eine Sweep-Methode und eine kleine Anzahl von Linien der endlichen Länge.

Answer 1

Alle Ihre Zeilen definieren eine planare Unterteilung , wobei jeder polygonale -Einrichtung durch eine endliche Anzahl von Liniensegmenten oder Strahlen begrenzt ist. Also müssen Sie zunächst eine (wahrscheinlich unendliche) Region finden, die einen Abfragepunkt enthält, und dann können Sie seine Grenzlinie mit minimalem Abstand von diesem Punkt auswählen.

Es gibt viele Möglichkeiten, um eine planare Unterteilung vorzubereiten, um das Lösen der Point Location Problem mit logarithmischer Zeitkomplexität. Eine einiger hierarchische Datenstruktur wird typischerweise erarbeitet, die für einen Abfragepunkt durchlaufen werden kann, und es ist erwiesen, dass die Länge des Traverse-Pfads durch $ O (log (n)) $ begrenzt ist (log (n)) $ , wobei $ n $ die Anzahl der Regionen ist. Wie @pseudonym in Kommentaren erwähnt, können Sie auch binäre Space Partitioning (BSP) zum Bau eines BSP-Baum - Es ist auch eine hierarchische Datenstruktur (binärer Baum), mit der Sie eine Region effizient finden können, die einen Abfragepunkt enthält. Es sieht so aus, als ob Ihr Problem gut für diesen BSP-Ansatz passt.

Es tut mir leid zu sagen, dass Sie Regionen mit $ O (n) $ Grenzsegmente / Strahlen erhalten, wobei $ n $ ist die Anzahl der Zeilen. Um diese Schwierigkeit zu überwinden, können Sie jede Region weiter in Voronoi-Diagramm , das für seine Grenzsegmente verallgemeinert ist Strahlen. Es ist leicht zu sehen, dass die Gesamtzahl derartiger raffinierter Region von $ O (N ^ 2) $ begrenzt wird, wodurch Sie noch eine logarithmische Zeitkomplexität für die nächstgelegene Zeile erhalten Suche. Im durchschnittlichen Fall werden diese Regionen jedoch mit vielen Grenzsegmenten / Strahlen jedoch einen kleinen Bruchteil aller Regionen ausmachen - somit können Sie im Durchschnitt immer noch schnell das nächstgelegene Grenzsegment / Ray auswählen, das nur durch Schleifen über die Regionengrenze schließen.

---

Wenn Sie mehr über allgemeine Eigenschaften der geometrischen Struktur erfahren möchten, ist es sinnvoll, diese Wiki-Seite.

Answer 2

Ich habe vielleicht Ihr Ziel missverstanden - nehmen Sie an, dass die Ränder in beide Richtungen weitergehen, auch wenn sie mit 2 spezifischen Punkten entlang definiert sind?Ich gehe davon aus, dass Sie sagen, dass der Abstand durch senkrechte Entfernung definiert ist.In diesem Fall wie geht es mit diesem Fall -
1. Berechnen Sie für jedes Zeilensegment den Winkel.
2. Zeichnen Sie eine imaginäre Linie, die Ihren willkürlichen Punkt in einem Winkel durchläuft, der senkrecht zum Liniensegment ist.
3. Finden Sie den Punkt der Kreuzung zwischen dem Liniensegment und der neuen imaginären Linie, finden Sie den Abstand zwischen diesem Punkt und Ihrem willkürlichen Punkt.Halten Sie die niedrigste Entfernung.
Wenn die Zeilen nicht unendlich lang sind, dann, wenn Sie den Abstand überprüfen, überprüfen Sie min (Abstand zum Startpunkt, Abstand zum Endpunkt).