Algorithmus zur Ermittlung von Wendepunkten für eine Polylinie

22

Ich versuche, die Wendepunkte herauszufinden, dh Punkte, an denen die Kurven in einer Linie beginnen und enden. Wenn Sie sich das Bild ansehen, ist die grüne Linie möglicherweise eine Straße oder ein Bach, und die schwarzen Punkte sind die Punkte, an denen die Kurven beginnen und enden. Bildbeschreibung hier eingeben

Was wären die übergeordneten Schritte, um die Generierung dieser Punkte zu automatisieren? Ich habe ArcGIS-Desktop und bin mit ArcObjects recht praktisch.

Devdatta Tengshe
quelle
Bei den Quelldaten handelt es sich um eine Polylinie aus Liniensegmenten, die Sie mit Kurven approximieren möchten, oder sind bereits Bogensegmente vorhanden?
U2ros
Derzeit besteht es aus Liniensegmenten.
Devdatta Tengshe
1
Die Abbildung in dieser Frage sieht bemerkenswert aus wie eine, die unter esri.com/news/arcuser/0110/turning.html veröffentlicht wurde .
Whuber
@whuber: Sehr scharfsinnige Beobachtung. Das war genau die Datenquelle, aus der ich das Image erstellt hatte.
Devdatta Tengshe

Antworten:

15

Wenn die Kurve aus Liniensegmenten besteht, sind alle inneren Punkte dieser Segmente Wendepunkte, was nicht interessant ist. Stattdessen sollte die Kurve als durch die Scheitelpunkte dieser Segmente angenähert angesehen werden . Indem wir eine stückweise doppelt differenzierbare Kurve durch diese Segmente splitten, können wir die Krümmung berechnen. Ein Wendepunkt ist dann genau genommen ein Ort, an dem die Krümmung Null ist.

Im Beispiel gibt es längere Strecken, in denen die Krümmung nahezu Null ist. Dies legt nahe, dass die angezeigten Punkte die Enden solcher Strecken von Regionen mit niedriger Krümmung approximieren sollten.

Ein effektiver Algorithmus wird daher die Eckpunkte splitten, die Krümmung entlang eines dichten Satzes von Zwischenpunkten berechnen, Bereiche mit einer Krümmung nahe Null identifizieren (unter Verwendung einer vernünftigen Schätzung dessen, was es bedeutet, "nahe" zu sein) und die Endpunkte dieser Bereiche markieren .

Im folgenden Arbeitscode Rwerden diese Ideen veranschaulicht. Beginnen wir mit einer Zeilenfolge, die als eine Folge von Koordinaten ausgedrückt wird:

xy <- matrix(c(5,20, 3,18, 2,19, 1.5,16, 5.5,9, 4.5,8, 3.5,12, 2.5,11, 3.5,3, 
               2,3, 2,6, 0,6, 2.5,-4, 4,-5, 6.5,-2, 7.5,-2.5, 7.7,-3.5, 6.5,-8), ncol=2, byrow=TRUE)

Spline die x- und y- Koordinaten getrennt , um eine Parametrisierung der Kurve zu erreichen. (Der Parameter wird aufgerufen time.)

n <- dim(xy)[1]
fx <- splinefun(1:n, xy[,1], method="natural")
fy <- splinefun(1:n, xy[,2], method="natural")

Interpolieren Sie die Splines zum Zeichnen und Berechnen:

time <- seq(1,n,length.out=511)
uv <- sapply(time, function(t) c(fx(t), fy(t)))

Wir benötigen eine Funktion, um die Krümmung einer parametrisierten Kurve zu berechnen . Es muss die erste und die zweite Ableitung des Splines geschätzt werden. Bei vielen Splines (z. B. kubischen Splines) ist dies eine einfache algebraische Berechnung. RLiefert die ersten drei Ableitungen automatisch. (In anderen Umgebungen kann es sinnvoll sein, die Ableitungen numerisch zu berechnen.)

curvature <- function(t, fx, fy) {
  # t is an argument to spline functions fx and fy.
  xp <- fx(t,1); yp <- fy(t,1)            # First derivatives
  xpp <- fx(t,2); ypp <- fy(t,2)          # Second derivatives
  v <- sqrt(xp^2 + yp^2)                  # Speed
  (xp*ypp - yp*xpp) / v^3                 # (Signed) curvature
  # (Left turns have positive curvature; right turns, negative.)
}

kappa <- abs(curvature(time, fx, fy))     # Absolute curvature of the data

Ich schlage vor, eine Schwelle für die Krümmung Null in Bezug auf die Ausdehnung der Kurve zu schätzen . Dies ist zumindest ein guter Ausgangspunkt; es sollte entsprechend der Tortuosität der Kurve angepasst werden (dh für längere Kurven erhöht). Dies wird später zum Färben der Diagramme entsprechend der Krümmung verwendet.

curvature.zero <- 2*pi / max(range(xy[,1]), range(xy[,2])) # A small threshold
i.col <- 1 + floor(127 * curvature.zero/(curvature.zero + kappa)) 
palette(terrain.colors(max(i.col)))                        # Colors

Nachdem die Scheitelpunkte gekerbt und die Krümmung berechnet wurden, müssen nur noch die Wendepunkte gefunden werden . Um sie zu zeigen, können wir die Eckpunkte zeichnen, den Spline zeichnen und die Wendepunkte darauf markieren.

plot(xy, asp=1, xlab="x",ylab="y", type="n")
tmp <- sapply(2:length(kappa), function(i) lines(rbind(uv[,i-1],uv[,i]), lwd=2, col=i.col[i]))
points(t(sapply(time[diff(kappa < curvature.zero/2) != 0], 
       function(t) c(fx(t), fy(t)))), pch=19, col="Black")
points(xy)

Handlung

Die offenen Punkte sind die ursprünglichen Eckpunkte in xyund die schwarzen Punkte sind die Wendepunkte, die mit diesem Algorithmus automatisch identifiziert werden. Da die Krümmung an den Endpunkten der Kurve nicht zuverlässig berechnet werden kann, sind diese Punkte nicht besonders markiert.

whuber
quelle
Vielleicht war die von mir verwendete Terminologie falsch. Was Sie angenommen haben, ist genau das, was ich wollte. Ihre Antwort sieht vielversprechend aus und ich muss mit R arbeiten, um mein Shapefile zu verarbeiten.
Devdatta Tengshe
3

Sie können das Verdichtungswerkzeug verwenden . In diesem Fall wählen Sie die Verdichtung nach Winkel. Wählen Sie anschließend den maximalen Winkel, der in einer geraden Linie zulässig ist. Dann auf die Ergebnislinie auf das Werkzeug Linie an Scheitelpunkten teilen anwenden . Löschen Sie abschließend die Linien, deren shape_length kleiner als die minimale Straßenlänge ist.

Bildbeschreibung hier eingeben

In diesem Bild sehen wir drei Schritte:

1- Verdichten Sie die Linie mit Winkel. Ich habe 10 Grad als Parameter verwendet, und wir haben splitline verwendet. Im Bild befindet sich die gekrümmte Linie in ihrer Anfangsphase.

arcpy.Densify_edit("line" , "ANGLE" , "","",10)
arcpy.SplitLine_management("line" , "line_split")

2- Wählen Sie die Segmente aus, bei denen shape_length nicht redundant ist. Wie wir in der Tabelle sehen, habe ich diese redundanten Längen nicht ausgewählt. Dann wähle ich sie in einer neuen Feature-Class aus.

arcpy.Select_analysis("line_split" , "line_split_selected")

3- Wir haben die Eckpunkte an den Kanten der Linien extrahiert, die Wendepunkte sind.

arcpy.FeatureVerticesToPoints_management("line_split_selected" , "line_split_pnt" , "DANGLE")
Geogeek
quelle
Ich habe die gleichen Kommentare und Fragen zu Ihrer anderen Antwort: Es ist eine nette Idee, aber gleichzeitig ist nicht klar, ob es das gewünschte Ergebnis bringt oder wie man den Schwellenwinkel wählen sollte. Können Sie die Ergebnisse veranschaulichen, damit die Leser bewerten können, was dieser Vorschlag wirklich leistet? Das Bereitstellen von Arbeitsbeispielen ist besonders wichtig, wenn Sie ESRI-Software als Teil einer Lösung empfehlen, da ihre Algorithmen normalerweise nicht dokumentiert sind und es daher unmöglich ist, genau zu wissen, was sie tun.
whuber
Um ganz sicher zu sein, dass dies eine funktionierende Lösung ist, muss ich sie testen, aber ich kann sie nicht testen. Ich vermisse die Daten. Ich gehe also davon aus, dass die von ESRI vorgeschlagenen Tools wie erwartet funktionieren werden, aber dies muss beantwortet werden weiter getestet werden.
Geogeek
wir könnten ihnen ideen nennen und keine antworten
geogeek
1
Möchten Sie, dass ich sie in Kommentare verschiebe? Übrigens, wenn Sie Daten testen möchten, können Sie zunächst die Koordinaten verwenden, die ich in meiner Antwort angegeben habe, da sie nahe an der Abbildung in der Frage liegen. Aber warum nicht einfach alle geografischen Daten verwenden, die Sie zur Hand haben?
Whuber
2
Ja, diese Lösung funktioniert wirklich besser, wenn es darum geht, nur gerade Linien zu extrahieren.
Geogeek
1

Sie können das Werkzeug " Generalisieren" verwenden, das den maximalen Versatz von der ursprünglichen Linie als Parameter hat, damit Sie den Versatz auswählen können, der zu Ihrem Fall passt.

Bildbeschreibung hier eingeben

Wenn wir die ursprüngliche Zeile "line_cur" und die verallgemeinerte Zeile "line_gen" nennen, könnten wir "line_cur" durch "line_gen" abschneiden. Das Ergebnis ist das gerade Segment von "line_cur". Dann könnten wir einige sehr kurze Segmente bereinigen, indem wir sie mit einer SQL-Abfrage löschen, die die Shape_Länge auswählt, die größer als die minimale Straßenlänge ist.

Geogeek
quelle
Das ist eine schöne Idee. Es ist jedoch nicht klar, wie gut es in der Praxis funktionieren würde. Könnten Sie vielleicht ein Beispiel zeigen, das die gefundenen Wendepunkte zeigt?
Whuber
Ich habe eine Bearbeitung vorgenommen, um ein Bild
einzufügen.
Ist etwas nicht klar, ich bin verfügbar, um Ihre Fragen zu beantworten?
Geogeek
In der Abbildung sind keine Wendepunkte erkennbar. Wo genau wären sie? Und wie soll man die Toleranz für die Verallgemeinerung wählen?
Whuber
Ich brauche einige Daten, um den Test durchzuführen, aber ich denke, wir sollten die Toleranz durch Experimente wählen
Geogeek