Algorithmus zum Finden des nächsten Segments zu einem Punkt unter vielen Segmenten (Reverse Geocoding)

Ich habe eine Reihe von Segmenten durch zwei Punkte definiert. Wie kann ich an einem bestimmten Punkt das nächstgelegene Segment finden?Algorithmus zum Finden des nächsten Segments zu einem Punkt unter vielen Segmenten (Reverse Geocoding)

Ich habe bereits einen Algorithmus geschrieben, der den Abstand zwischen einem Punkt und einem Segment berechnet. Anyway Berechnung solcher Abstand für jedes Segment und dann wählen Sie das Segment mit dem niedrigsten Abstand ist nicht wirklich effizient :(

Da die Segmente Straßen darstellen, ist dies eigentlich ein Reverse GeoCoding-Problem, so hoffe ich, es gibt bekannte Lösungen zu diesem Problem ...

VIELEN DANK!

Quelle

2010-08-06 Giorgio

Ist die Menge der Segmente in irgendeiner Weise sortiert? –

Überlappen sich die Segmente? Meinst du Segmente auf einer Linie oder z.B. spherig Segmente? Wenn Letzteres, wie definieren Ihre zwei Punkte das Segment? (unterschiedliche Definitionen sind möglich) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ – peterchen

@Giorgio: Haben Sie den Algorithmus gefunden? Könnten Sie mir bitte einen Link zu diesem Algorithmus geben oder geben? Vielen Dank im Voraus! –

Verwenden Sie ein Gitter, kd-Baum, Quadtree oder ähnliche binary space Partitioning-Methode. Dann wird aus der Zelle Baum, die Ihren Punkt in liegt, beginnen Segmente, bis die Erkundung Abstand von dem Punkt zu der Zelle, die das Segment enthält, ist größer als der kleinste bisher gefundene Abstand

http://en.wikipedia.org/wiki/Binary_space_partitioning

(Dies ist natürlich unter der Annahme, dass die Segmente/Straßen nur sehr selten ändern, aber Sie haben eine Menge Punkte lokalisieren zu).

Quelle

2010-08-06 12:57:03

Es gibt keine Möglichkeit zu wissen, ob ein bestimmtes Segment eine bestimmte Partition schneidet, ohne eine (mindestens) gleich teure Berechnung (im Vergleich zur Punktsegmententfernung) durchzuführen. Daher wäre jeder Partitionierungsansatz möglicherweise nur schneller, wenn die Menge der Segmente vorhanden wäre erfüllt bestimmte Bedingungen (zB maximale Segmentlänge << Partitionsabmessungen). – MusiGenesis

@MusiGenesis: Der Schlüssel ist, jedes Segment zu einem Teil aller Blätter zu machen, die es schneidet, wenn der Baum konstruiert wird. Wenn eines der Blätter nahe genug an den Punkten ist, wird das Segment getestet. Wenn keines der Blätter nah genug ist, wird das Segment nie getestet. Da der Baum nur einmal erstellt wird, werden die Kosten dafür auf alle nachfolgenden Anfragen verteilt. –

vereinbart. Ich nahm an, dass es jedes Mal eine andere Gruppe von Segmenten gibt. – MusiGenesis

Algorithmus zum Finden des nächsten Segments zu einem Punkt unter vielen Segmenten (Reverse Geocoding)

Antwort

Verwandte Themen