Algorithmen zum Abgleichen von Segmenten

Was sind die besten Algorithmen, um Segmente abzugleichen?

Ich versuche, entsprechende Segmente aus zwei Kartenquellen abzugleichen, eines weniger genau, aber mit Segmentnamen, und eines genauer ohne Segmentnamen. Ich möchte die Segmentnamen halbautomatisch auf die genauere Karte anwenden.

Der angeforderte Algorithmus hat eine ziemlich vage Beschreibung, da eine "Übereinstimmung" nicht gut definiert ist und viele Faktoren (Orientierung, relative Länge, Entfernung) in verschiedenen Szenarien unterschiedliche Gewichtung haben können. Ich bin jedoch auf der Suche nach Grundkenntnissen über die allgemeinen Ansätze zur Behandlung dieses Problems.

Arbeitsimplementierungen für Open-Source-Umgebungen (PostGIS, shapely, ...) sind herzlich willkommen.

Beispielsegmente : Siehe Beschreibung unter Bilder.

Der Hausdorff-Abstand kann verwendet werden: Übereinstimmende Segmente können gemäß diesem Abstand "enge" Segmente sein. Es ist ganz einfach, nach Segmenten zu berechnen.

Eine kostenlose Java-Implementierung ist in JTS verfügbar - siehe JTS Distance Package . Sie können sich auch die JCS Conflation Suite ansehen (jetzt aufgegeben, Kopie der Quellen, z . B. unter https://github.com/oschrenk/jcs ).

Ich weiß nicht, was das "Beste" wäre, denn das hängt von den Einzelheiten Ihrer Segmente ab.

Ein allgemein guter Ansatz besteht darin, die Segmente in entscheidende geometrische Informationen zu zerlegen . Dies würde mindestens die Position des Zentrums (x, y), die Ausrichtung (0 bis 180 Grad) und die Länge umfassen. Mit geeigneten Gewichtungen und einer gewissen Feinabstimmung der Ausrichtung (da 180 auf 0 zurückgesetzt wird) können Sie dann fast jeden statistischen Clustering-Algorithmus auf die Sammlung aller Segmente anwenden . ( K-means wäre eine gute Option, aber die meisten hierarchischen Methoden sollten gut funktionieren. Solche Cluster-Analysen sind in der Regel schnell und einfach anzuwenden.) Idealerweise werden die Segmente paarweise (oder Singletons für nicht übereinstimmende Segmente) und die übrigen Segmente ausgeführt ist einfach.

Eine Möglichkeit, mit dem Orientierungsproblem umzugehen, besteht darin, eine Kopie der beschrifteten Segmente zu erstellen. Fügen Sie der Ausrichtung der ersten Kopie 180 Grad hinzu, wenn sie kleiner als 90 ist, und subtrahieren Sie ansonsten 180 Grad von der Ausrichtung. Dies vergrößert Ihren Datensatz (offensichtlich), ändert aber ansonsten den Algorithmus in keiner Weise.

Gewichte werden benötigt, da Unterschiede bei Koordinaten, Längen und Ausrichtungen hinsichtlich der Ähnlichkeiten der entsprechenden Segmente sehr unterschiedliche Bedeutungen haben können. In vielen Anwendungen ergeben sich Unterschiede zwischen Segmenten aus Unterschieden in den Positionen ihrer Endpunkte. Als grobe Näherung können wir erwarten, dass die typische Variation der Segmentlängen in etwa der typischen Variation zwischen ihren Endpunkten entspricht. Daher sollten die mit x, y und Länge verknüpften Gewichte ungefähr gleich sein. Der schwierige Teil ist die Gewichtung der Orientierung, da Orientierung nicht mit Distanz gleichgesetzt werden kann und, noch schlimmer, kurze Segmente mit größerer Wahrscheinlichkeit falsch ausgerichtet sind als lange Segmente. Stellen Sie sich eine Trial-and-Error-Methode vor, die ein paar Grad an Fehlausrichtung mit der Größe einer typischen Lücke zwischen Segmenten gleichsetzt und diese dann so lange anpasst, bis das Verfahren anscheinend gut funktioniert. Zur Orientierung lassenL ist eine typische Segmentlänge. Eine Änderung der Ausrichtung um einen kleineren Winkel von t Grad überstreicht einen Abstand von ungefähr L / 2 · t / 60 (der Abstand von 60 entspricht ungefähr der Gradzahl in einem Bogenmaß), der L / 120-mal t ist . Das schlägt vor, mit Einheitsgewichten für x, y und Länge und einem Gewicht von L / 120 für die Orientierung zu beginnen.

Zusammenfassend ist dieser Vorschlag:

1. Erstellen Sie Kopien der beschrifteten Segmente (wie im Abschnitt zur Feinabstimmung der Ausrichtung beschrieben).

2. Konvertieren Sie jedes Segment in das Vierfache (x, y, Länge, L / 120 * Ausrichtung), wobei L eine typische Segmentlänge ist.

3. Führen Sie eine Clusteranalyse der Quadrupel durch. Verwenden Sie ein gutes Statistikpaket ( R ist kostenlos).

4. Verwenden Sie die Clusteranalyse-Ausgabe als Nachschlagetabelle, um beschriftete Segmente nicht beschrifteten Segmenten in der Nähe zuzuordnen.

Ich habe vor ungefähr 5 Jahren an einem Projekt mit ähnlichen Anforderungen gearbeitet. Dabei wurden die Koordinaten der Straßenmittellinien (mit relativ hoher Koordinatengenauigkeit) mit den Verkehrsnetzverbindungen des Highway Performance Monitoring System (HPMS) kombiniert.

Zu diesem Zeitpunkt stellte die FHWA noch keine Werkzeuge zur Verfügung. Das könnte sich geändert haben, möchten Sie vielleicht überprüfen. Auch wenn Sie nicht mit Autobahndaten arbeiten, sind die Tools möglicherweise immer noch relevant.

Ich habe es mit ArcGIS geschrieben, aber der Algorithmus sollte in OpenSource funktionieren, sofern er Ablaufverfolgungsfunktionen bietet, die denen von ISegmentGraph ähneln :

// features is a collection of features with higher geometry
// Links are a collection features with attributes but low res geometry
For each Link in lowResFeatureclass
    point startPoint = SnapToClosestPoint(Link.StartPoint, hiResfeatures);
    if(startPoint == null)
       continue;
    point endPoint = SnapToClosest(Link.EndPoint, hiResfeatures);
    if(endPoint == null)
       continue;
    polyline trace = Trace(hiResfeatures,startPoint,endPoint);
    if(polyline != null)
    {
        // write out a link with high precision polyline
        Write(Link,polyline);
    }
Next Link

Hier kommt eine Idee

Wenn Sie eine der Linienreihen zerreißen, um zu vergleichen und zu testen, ob sich die Vertexpoints in einem gewissen Abstand von der anderen Linienreihe zum Vergleichen befinden, können Sie den Test auf viele Arten steuern.

diese Beispiele funktionieren in PostGIS (wer könnte raten :-))

Erstens, wenn wir sagen, dass es eine Übereinstimmung gibt, wenn alle Eckpunkte in einer Linienfolge in Tabelle_1 0,5 Meter (Karteneinheiten) oder näher an einer Linienfolge in Tabelle_2 liegen:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points,
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(*)=num_of_points;

Dann können wir sagen, dass es eine Übereinstimmung gibt, wenn mehr als 60% der vertex_points in einer Linienfolge in Tabelle_1 innerhalb des Abstands einer Linienfolge in Tabelle_2 liegen

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)/num_of_points::float > 0.6

Oder wir können akzeptieren, dass ein Punkt nicht in Reichweite ist:

SELECT a.id, b.id FROM
(SELECT ST_NPoints(the_geom) as num_of_points, 
(ST_Dumppoints(the_geom)).geom as p, id FROM table_1) a 
INNER JOIN 
table_2 b 
ON ST_DWithin(a.p, b.the_geom, 0.5) GROUP BY a.id, b.id
HAVING COUNT(b.id)-num_of_points <= 1;

Sie müssen die Abfrage auch mit Tabelle_1 und Tabelle_2 in vertauschten Rollen ausführen.

Ich weiß nicht, wie schnell es sein wird. ST_Dumppoints ist derzeit eine SQL-Funktion in PostGIS und keine C-Funktion, die es langsamer macht, als es sein sollte. Aber ich denke, es wird trotzdem ziemlich schnell gehen.

Raumindizes helfen ST_D sehr dabei, effektiv zu sein.

HTH Nicklas

Ich habe Code geschrieben, um die Suche nach schlampigen Liniensegmenten (und deren Überlappung) in Boundary Generator zu handhaben. Ich habe die (ziemlich elementare) Mathematik dahinter hier geschrieben: http://blog.shoutis.org/2008/10/inside-boundary-generator-computational.html . Der Code ist Open Source und von diesem Blogbeitrag verlinkt.

Der Code folgt einem sehr einfachen Ansatz:

• Ein Segment-Segment-Test, der Aufschluss darüber gibt, ob sich zwei Liniensegmente innerhalb vorgegebener Winkel- und Abstandstoleranzen überlappen, sowie über den Umfang der Überlappung.
• Ein schneller räumlicher Index, mit dem nicht mehr jedes Liniensegment im Dataset mit allen anderen Liniensegmenten im Dataset verglichen werden muss.

Der Hauptvorteil dieses Ansatzes besteht darin, dass Sie präzise Knöpfe für gültigen Winkel, Abstände und Überlappungslänge erhalten. Auf der anderen Seite ist dies keine Methode, um die Ähnlichkeit zweier Liniensegmente allgemein zu messen. Es ist also viel schwieriger, z. B. statistische Cluster zu erstellen, um wahrscheinliche Übereinstimmungen zu ermitteln.

Hinweis: Ich vermute, dass Sie mit genügend SQL-Chops den Segment-Segment-Test in eine WHERE-Klausel packen könnten ... :)

Prost!

Ich habe einen groben Prototyp für Map - Matching implementiert hier , die leicht zu bedienen ist relativ. Es basiert auf der Open Source Routing Engine und ist in Java geschrieben. Der verwendete Algorithmus wird hier beschrieben .