Ermitteln der ungefähren Überlappungen einer gegebenen Polylinie mit einer Menge bestehender Polylinien

Question

Ich habe eine Reihe von Polylinien (Nummerierung in 100er, wobei jede Polylinie etwa 200-300 Ecken hat). Diese repräsentieren Routen auf einer Karte (alle aus der Google Maps API, falls das hilft). Die Scheitelpunkte sind Breiten-/Längenkoordinaten.

Ich habe jetzt eine Abfrage Polylinie, und ich muss die "Überlappungen" der Abfrage Polylinie mit einem der vorhandenen Polylinien finden. Die Ergebnisse werden somit selbst Polylinien sein, sortiert in der Reihenfolge von Maximum zu geringster Überlappung. Ich brauche nur die ersten 100 Ergebnisse oder so. Ein zusätzliches Problem ist, dass die Überlappung nicht exakt sein muss, sondern angenähert sein kann (d. H. Abschnitte von Liniensegmenten, die als überlappend betrachtet werden, müssen nicht aufeinander liegen, sondern müssen nur "nahe beieinander" sein).

Um eine konkrete Darstellung zu geben, ist im linken Teil des Bildes die blaue Polylinie (Polylinie A) eine Polylinie in der Datenbank und die rote Polylinie (Polylinie B) die Query-Polylinie. Der Algorithmus sollte die Polylinie bestimmen, die in dickem Schwarz markiert ist, wie rechts gezeigt.

Ich bin derzeit Neigung zu einer räumlichen Datenbank (die Option in Betracht gezogen wird PostgreSQL + PostGIS), aber ich bin mir nicht sicher, dass die Latenz akzeptabel wäre - die Abfrage muss Ergebnisse in der Nähe sofort zurückzukehren. Mein Berechnungs-Geometrie-Fu ist zugegebenermaßen schwach, aber ich frage mich: Gibt es irgendwelche Algorithmen oder Ansätze, die sich als nützlich erweisen könnten, um dieses spezielle Problem zu lösen?

Vielen Dank im Voraus!

Answer 1

Schnelle ungefähre Abfrage, wo Sie nicht alle Übereinstimmungen finden müssen riecht wie http://en.wikipedia.org/wiki/Locality-sensitive_hashing - und ich vermute, dass Sie eine Menge Treffer mit diesem erhalten werden. Vor einiger Zeit war ich fasziniert von http://www.cs.ubc.ca/~lowe/papers/09muja.pdf - ich habe keine Ahnung, ob es in der Praxis funktioniert, aber die gleiche Suche, die das Papier wiedergefunden hat, fand eine Bibliothek bei http://www.cs.ubc.ca/research/flann/. Die Wikipedia-Seite auf der geraden LSH hat auch Hinweise auf mindestens eine Implementierung unten. LSH hat den Vorteil, dass es nahtlos in die Datenbanksuche mit relationalen Datenbanken oder dbm-Dateien übersetzt werden kann.

Answer 2

Betrachten Sie zunächst nur die Begrenzungslinien der Linien - so wird eine Linie von (x1,y1)->(x2,y2) zu einem Rechteck (x1,y1,x2,y2). Das Nachschlagen von Überlappungen zwischen einer Begrenzungsbox und den anderen kann in O (log n) -Zeit unter Verwendung einer zweidimensionalen interval tree oder segment tree erfolgen. Sie könnten dann über diese potenziellen Übereinstimmungen iterieren, um zu überprüfen, ob sich die Linien tatsächlich schneiden. Die gesamte Zeitkomplexität wäre ungefähr O (n log n) für alle Zeilen mit Datensätzen mit wenigen überlappenden Begrenzungsboxen.

Es gibt einen Stackoverflow Post mit einer guten Beschreibung, wie man test if two lines intersect

Answer 3

die großen Problem Größe gegeben, schlage ich vor, dass Sie mit einer Rasterung Ansatz beginnen. Ich meine ein quadratisches Gitter über der Karte zu überlagern, und für jede Kachel (nennen wir sie Pixel) eine Liste der Polylinien, die sie überqueren. In gewisser Weise läuft dies darauf hinaus, eine Raster-Scan-Umwandlung der Karte unter Verwendung des Bresenham-Algorithmus oder einer Variante durchzuführen.

In ähnlicher Weise können Sie die Query-Polylinie zeichnen und alle Polylinien sammeln, die ein oder mehrere Pixel mit der vorherigen teilen. Sie können die gemeinsamen Pixel zählen, um eine erste Schätzung der Überlappungslänge zu erhalten. Es kann ratsam sein, eine "dicke" Linie zu zeichnen, um die Ungenauigkeiten aufgrund der Diskretisierung zu absorbieren.

Nach diesem ersten Screening-Durchlauf wird die Anzahl der zu betrachtenden Polylinien erheblich geringer sein, so dass jeder Brute-Force-Ansatz zur Überlappungsbewertung verwendet werden kann.

Ein kritisches Problem ist die Rasterauflösung. Zu grob wird zu einer ineffizienten Kandidatenzurückweisung führen. Zu fein wird Vorverarbeitungszeit/-raum in einer inakzeptablen Weise erhöhen.

Unter der Annahme einer Rastergröße, dass Sie W x H Pixel haben, benötigen Sie W x H verknüpfte Listenzeiger plus N x L Zeiger (für N Polylinien der durchschnittlichen Länge L, in Pixel - nicht in Vertex-Anzahl). Der erste Term wächst als Quadrat der Auflösung, während der zweite nur linear wächst. Die Vorverarbeitungszeit ist linear in der Größe dieser Datenstruktur (W × H zum Initialisieren der Listen, N × L für Bresenham-Linienzeichnungen).

Eine Abfrage kostet etwa L 'x K, wobei L' die Länge der Query-Polylinie und K die Anzahl der gefundenen überlappenden Polylinien ist (im Fall K >> 1 eine effiziente Dictionary-Struktur für die Buchhaltung der K Kandidaten). Dies ist proportional zur Auflösung.

PS: Wenn die gewählte Auflösung so ist, dass Sie nicht mehr als eine Polylinie pro Pixel annehmen können (dies ist eine Annäherung), dann vereinfacht der Algorithmus: Zeichnen Sie die gesamte Karte, jede Polylinie in einer anderen Farbe; Zeichnen Sie dann die Query-Polylinie und notieren Sie sich die Farben, die Sie kreuzen. Genau das hast du skizziert!