Messen der Geradheit eines Kurvensegments (dargestellt als Polylinie)

11

Ich arbeite an einem automatischen Algorithmus zur Beschriftung von Höhenkonturen. Einer der Faktoren, die ich bei der Entscheidung über die Position von Beschriftungen berücksichtigen möchte, ist, wie "gerade" ein bestimmtes Segment einer Kontur ist. Je gerader es ist, desto wahrscheinlicher ist es, dass das Etikett auf diesem Segment platziert wird.

Jede Kontur wird durch eine Polylinie dargestellt (jedoch mit Punkten nahe beieinander, die mit bloßem Auge wie eine Kurve aussehen). Ich habe dann eine feste Länge (Breite eines Etiketts), beispielsweise 100 Pixel. Wenn ich zufällig (oder auf andere Weise) ein Kontursegment mit einer Breite von 100 Pixeln auswähle, möchte ich in der Lage sein, einen numerischen quantitativen Wert seiner Geradheit zu erhalten (z. B. Null für ein vollständig gerades Kontursegment, ein Wert größer als Null für ein Nicht so gerades Segment, und dieser Wert steigt mit zunehmender Krümmung).

Ich habe nach Antworten gesucht, aber nichts wirklich Nützliches gefunden. Ich wäre dankbar für Hinweise.

Igor Brejc
quelle

Antworten:

9

Die Antwort hängt vom Kontext ab : Wenn Sie nur eine kleine (begrenzte) Anzahl von Segmenten untersuchen, können Sie sich möglicherweise eine rechenintensive Lösung leisten. Es ist jedoch wahrscheinlich, dass Sie diese Berechnung in eine Art Suche nach guten Beschriftungspunkten einbeziehen möchten. In diesem Fall ist es von großem Vorteil, eine Lösung zu haben, die entweder rechnerisch schnell ist oder eine schnelle Aktualisierung einer Lösung ermöglicht, wenn das Kandidatenliniensegment geringfügig variiert wird.

Zum Beispiel : Angenommen , Sie eine systematische Suche durchzuführen beabsichtigtüber eine gesamte verbundene Komponente einer Kontur, dargestellt als eine Folge von Punkten P (0), P (1), ..., P (n). Dies würde durch Initialisieren eines Zeigers (Index in der Sequenz) s = 0 ("s" für "Start") und eines anderen Zeigers f (für "Ende") erfolgen, um der kleinste Index zu sein, für den Abstand (P (f), P (s))> = 100, und dann s so lange vorrücken, wie die Entfernung (P (f), P (s + 1))> = 100. Dies erzeugt eine Kandidatenpolylinie (P (s), P (s +) 1) ..., P (f-1), P (f)) zur Bewertung. Nachdem Sie die "Eignung" zur Unterstützung eines Labels bewertet haben, erhöhen Sie s um 1 (s = s + 1) und erhöhen f auf (sagen wir) f 'und s auf s', bis erneut eine Kandidatenpolylinie das Minimum überschreitet Es wird eine Spanne von 100 erzeugt, dargestellt als (P (s '), ... P (f), P (f + 1), ..., P (f')). Dabei werden die Eckpunkte P (s) ... P (s ' Es ist sehr wünschenswert, dass die Fitness schnell aktualisiert werden kann, wenn nur die abgelegten und hinzugefügten Eckpunkte bekannt sind. (Dieser Scanvorgang würde fortgesetzt, bis s = n; wie üblich muss f dabei erlaubt sein, von n zurück auf 0 zu "wickeln".)

Diese Überlegung schließt viele mögliche Fitnessmaße ( Sinuosität , Tortuosität usw.) aus, die ansonsten attraktiv sein könnten. Dies führt dazu, dass wir L2- basierte Kennzahlen bevorzugen , da diese normalerweise schnell aktualisiert werden können, wenn sich die zugrunde liegenden Daten geringfügig ändern. Eine Analogie zur Hauptkomponentenanalyse legt nahe, dass wir das folgende Maß haben (wobei klein besser ist, wie gewünscht): Verwenden Sie den kleineren der beiden Eigenwerte der Kovarianzmatrixder Punktkoordinaten. Geometrisch ist dies ein Maß für die "typische" Abweichung von Seite zu Seite der Eckpunkte innerhalb des Kandidatenabschnitts der Polylinie. (Eine Interpretation ist, dass seine Quadratwurzel die kleinere Halbachse der Ellipse ist, die die zweiten Trägheitsmomente der Eckpunkte der Polylinie darstellt.) Sie ist nur für Sätze kollinearer Eckpunkte gleich Null. Andernfalls wird Null überschritten. Es misst eine durchschnittliche Abweichung von Seite zu Seite relativ zur 100-Pixel-Grundlinie, die durch den Beginn und das Ende einer Polylinie erzeugt wird, und hat dadurch eine einfache Interpretation.

Da die Kovarianzmatrix nur 2 mal 2 ist, werden die Eigenwerte schnell durch Lösen einer einzelnen quadratischen Gleichung gefunden. Darüber hinaus ist die Kovarianzmatrix eine Summe der Beiträge von jedem der Eckpunkte in einer Polylinie. Daher wird es schnell aktualisiert, wenn Punkte entfernt oder hinzugefügt werden, was zu einem O (n) -Algorithmus für eine n-Punkt-Kontur führt: Dies lässt sich gut auf die in der Anwendung vorgesehenen sehr detaillierten Konturen skalieren.

Hier ist ein Beispiel für das Ergebnis dieses Algorithmus. Die schwarzen Punkte sind Eckpunkte einer Kontur. Die durchgezogene rote Linie ist das beste mögliche Polyliniensegment mit einer End-to-End-Länge von mehr als 100 innerhalb dieser Kontur. (Der visuell offensichtliche Kandidat oben rechts ist nicht lang genug.)

Zahl

whuber
quelle
Wow, du hast mich dort verloren :). Sie haben Recht mit der systematischen Suche. Ich muss dies bereits tun, um die Tangente jedes Polylinien- / Polygonscheitelpunkts zu ermitteln (horizontale Beschriftungen werden vertikalen vorgezogen). Theoretisch könnte ich diese Suche also auf andere Messungen ausweiten. Übrigens: Haben Sie das Beispieldiagramm mit einem tatsächlichen Algorithmus oder manuell erstellt?
Igor Brejc
1
Die Abbildung ist real, aber die von mir verwendete Implementierung verwendet nicht das Kovarianzaktualisierungsverfahren und ist daher nicht rechnerisch optimal.
whuber
2
Die Grafik am Ende macht diese Antwort noch
beeindruckender
2
Igor, ich sollte erwähnen, dass die Beschriftungsrichtung kostenlos ist: Sie ist gegeben durch die Richtung der Hauptachse der Ellipse (der dem größeren Eigenwert zugeordnete Eigenvektor). Sie können daher gleichzeitig effizient nach der besten Kombination aus Etikettenorientierung und Linearität des Konturabschnitts suchen.
whuber
3

In der Computergrafik-Community ist es häufig erforderlich, einen Begrenzungsrahmen um ein Objekt zu finden. Folglich ist dies ein gut untersuchtes Problem mit schnellen Algorithmen. Siehe beispielsweise den Artikel über Mindestbegrenzungsrahmenalgorithmen von Wikipedia . Sie können das Rechteck mit der minimalen Fläche finden, das Ihre Polylinie umgibt, und dann das Seitenverhältnis des Rechtecks, Höhe / Länge, verwenden. Um ein genaueres Maß zu erhalten, können Sie die Abweichung der Polylinie von der Mittellinie dieses Begrenzungsrechtecks ​​betrachten.

Joseph O'Rourke
quelle
1
Ich habe darüber nachgedacht, min. Begrenzungsrahmen, aber ich sehe zwei Probleme: a) Rechenaufwand bei der Berechnung eines Rahmens, der wirklich ein Minimum wäre (und somit gedreht wird), b) zwei Kurvensegmente mit demselben Seitenverhältnis können eine sehr unterschiedliche Krümmung aufweisen (denken Sie an eine Sinuskurve) Kurve mit gleicher Amplitude, aber unterschiedlichen Wellenperioden).
Igor Brejc
1
Es ist schön, Sie hier auf den GIS-Seiten zu sehen, Joseph!
whuber
1
Ja, ich habe gerade Ihr Buch "Computational Geometry in C" in meinen Händen :)
Igor Brejc
1
Vielen Dank für die Begrüßung an alle! :-) Mir ist klar, dass mein Vorschlag nicht die ideale Maßnahme ist, aber die Codierung ist von der Stange (wenn Sie das richtige Regal haben). Diese Art von Problem wurde in Fertigungskontexten, in denen die Qualität eines bearbeiteten Teils gemessen werden muss, eingehend untersucht.
Joseph O'Rourke
3

Ich weiß nicht, ob dies hilft oder ob es als Antwort gilt, aber als ich hier saß und über die Frage nachdachte, die ich gerade gestellt habe, hatte ich einen Gedanken:

Was ist, wenn Sie einen Kreis mit einem bestimmten Radius auf Ihrer Konturlinie platzieren? Dieser Kreis schneidet die Konturlinie an mindestens zwei Stellen. Je gerader die Linie ist, desto kürzer ist der Abstand entlang der Konturlinie zwischen den beiden Schnittpunkten. Je länger der Abstand entlang der Konturlinie zwischen den Schnittpunkten ist, desto gekrümmter ist die Linie. Wenn es mehr als zwei Schnittpunkte gibt, ist die Konturlinie viel zu kurvig.

Sie können herausfinden, welche Länge den besten Indikator für die Geradheit liefert, und eine Routine einrichten, um entlang jeder Konturlinie zu gehen und das Etikett dort zu platzieren, wo es gerade genug ist.

Ich bin mir sicher, dass dies nicht allzu viel hilft, und was ich auf Englisch sage, ist in der von Ihnen verwendeten Programmiersprache viel schwieriger, aber es könnte ein Anfang sein?

Rex-H
quelle
Interessante Idee. Zur Vereinfachung können Sie das Verhältnis zwischen der Länge des Segments auf einer Seite und dem Abstand zwischen Start- und Endpunkt berechnen. Es ist nicht so genau, aber es ist schnell zu berechnen. Und Ihre Idee, einen Kreis zu verwenden, würde eine genauere Berechnung der Geradheit ermöglichen.
Igor Brejc
3

Der einfachste Ansatz, den ich mir vorstellen kann, ist das Verhältnis zwischen der tatsächlichen Pfadlänge zwischen Start und Ende und dem kürzesten Abstand (gerade Linie) vom Anfang bis zum Endpunkt. Gerade Linien haben Verhältnisse nahe eins, während sehr gekrümmte Linien ein sehr hohes Verhältnis haben.

Dies sollte eine wirklich einfach zu implementierende Lösung sein.


Update: Wie Mike richtig bemerkte, würde dies Sinuosity entsprechen .

Geben Sie hier die Bildbeschreibung ein

Unterdunkel
quelle
Genau das, was mir nach dem Lesen von Rex 'Antwort in den Sinn kam :)
Igor Brejc
4
im Grunde das Gegenteil
Mike T
genau :) ....
underdark
2
Sie haben Recht, dass dies einfach zu implementieren ist, da das Aktualisieren der Länge bei der Suche nach geeigneten Segmenten zum Beschriften so einfach ist wie das Hinzufügen und Subtrahieren von Längen zwischen aufeinanderfolgenden Scheitelpunkten. Die Sinuosität erfasst jedoch nicht effektiv den Sinn, in dem eine Kurve von der Linearität abweichen kann. Vergleichen Sie beispielsweise einen Halbkreis mit einem Durchmesser von 100 mit einer linearen Folge von Halbkreisen mit einem Durchmesser von 1 : Beide Kurven haben die gleiche Sinuosität, aber die Abweichung von Seite zu Seite der ersten beträgt das 100-fache der Abweichung der zweiten (was eine schöne Basis wäre für ein Etikett).
whuber
Berücksichtigen Sie, dass diese Methode eine unendliche Sinuosität ergibt, wenn Ihre Polylinie einen Kreis zeichnet, was möglicherweise nicht das gewünschte Ergebnis ist.
obchardon
1

Durch die Suche nach "Krümmung" und "Polylinie" habe ich diese Informationen erhalten. Wie kann ich die Krümmung einer Polylinie finden? . Dort schlug er vor, zur Definition der Krümmung zurückzukehren - K= DF/Ds. Hier Fmeint er phioder Tin Wikipedia-Notation hier ( http://en.wikipedia.org/wiki/Curvature ).

Angenommen, Sie haben eine Sequenz mit drei Punkten, p0, p1 und p2. Berechnen Sie den Abstand szwischen p0 und p1, der das Delta von s ( Ds) ist, unter der Annahme, dass die Punkte nahe genug beieinander liegen. Dann benötigen Sie das Delta von T ( DT), dh die Änderung des Einheitstangentialvektors zwischen p0 und p1. Es mag einen ausgeklügelten Weg geben, aber die grobe Methode, die ich mir vorstellen kann, zwei Bektoren p0-> p1, p1-> p2 zu nehmen, jede auf eine Länge von eins zu normalisieren und dann die Vektorsubtraktion dieser beiden zu nehmen und dann die Größe zu bestimmen. Das ist DT. Division ergeben eine Krümmung K0_1. Nimm p1, p2 und p3 zum Berechnen K1_2und so weiter.

Ich frage mich jedoch, ob Sie die Kontur als Polylinie und nicht als gerenderte Pixel erfassen. Du hast 100px gesagt, damit ich mir ein bisschen Sorgen mache.

Yosukesabai
quelle
Danke für den Link, ich muss die Mathematik dahinter studieren. Ich habe 100px erwähnt, nur weil der gerenderte Beschriftungstext eine bestimmte Breite (in Pixel) hat. 100px war nur ein Beispiel.
Igor Brejc
An Krümmung zu denken ist eine schöne Idee. Eine Krümmung über stark geglättete Konturabschnitte mit ausreichender Länge mag angemessen sein, die Krümmung selbst jedoch nicht: Ein einzelner kleiner Zickzack hätte beispielsweise eine extrem hohe Krümmung, wäre aber insgesamt belanglos. Tatsächlich würden Sie also eine statistische Zusammenfassung der Abweichung von der Linearität über Abschnitte der Polylinie verwenden. Unter den wahrscheinlichen Kandidaten wäre die Krümmung eine der komplexeren Berechnungen.
whuber