Visvalingam-Whyatt-Polylinie Vereinfachung Algorithmus Klärung
Ich versuche zu realisieren eine Polylinie Vereinfachung Algorithmus. Der original Artikel kann hier gefunden werden: http://archive.is/Tzq2. Es scheint einfach im Konzept, aber ich verstehe nicht das Beispiel-Algorithmus (ich glaube, es ist schlecht formuliert) pseudocode geliefert und hatte gehofft, jemand könnte einige Einblicke. Aus dem Artikel konnte ich entnehmen, dass die grundlegende Idee ist,
- Berechnen Sie die effektive Fläche (gebildet durch das Dreieck zwischen den drei aufeinanderfolgende Punkte auf einer Linie) für jeden Punkt, und löschen Sie diese mit 0 Fläche
- Beginnend mit dem kleinsten Bereich, zu vergleichen, den Punkt der Gegend mit einem Schwellenwert, und, wenn der Bereich unterhalb dieser Schwelle, löschen Sie es aus der Polylinie.
- Zu bewegen, um die zwei benachbarten Punkte und berechnen Ihren Bereichen, wie Sie geändert haben
- Gehen Sie zurück zu 2, bis alle Bereiche, die unter der Schwelle entfernt wurden
Sich der Algorithmus wie folgt (wortwörtlich kopiert aus dem Artikel):
- Berechnen Sie die effektive Fläche jeder Punkt
Löschen Sie alle Punkte mit der Fläche null und speichern Sie diese in einer separaten Liste angezeigt, die mit diesem Bereich - WIEDERHOLEN
- Finden Sie den Punkt mit der geringsten effektiven Bereich und rufen Sie den aktuellen Punkt. Wenn der berechnete Bereich ist weniger als bei den letzten Punkt zu beseitigen, verwenden Sie dessen Umgebung statt. (Dies gewährleistet, dass der aktuelle Punkt nicht beseitigt werden kann, ohne die Beseitigung der zuvor eliminierten Punkte.)
- Löschen Sie den aktuellen Punkt aus der ursprünglichen Liste und fügen Sie diese an die neue Liste zusammen mit der Ihr zugeordneten Bereich, so dass die Zeile gefiltert werden kann, zur Laufzeit.
- Neu berechnen, die wirksame Fläche der beiden benachbarten Punkte (siehe Abbildung 1b).
- BIS
- Das original-line besteht aus nur 2 Punkte, nämlich die start-und end-Punkte.
Ich bin verwirrt mit der "wenn" - Klausel, die im ersten Schritt unter "WIEDERHOLEN" ... könnte jemand klären?
- Warum klingt das wie der Titel einer episode von "The Big Bang Theory" für mich?
- Denn Sie sehen zu viel TV 🙂
- Lol naja eigentlich col (kichern)
- der Artikel-link ist kaputt
- Funktioniert gut für mich. Vielleicht war es eine intermittierende Problem. Für die Referenz ist der Artikel mit dem Titel der Linie Verallgemeinerung durch Wiederholte Elimination der Kleinsten Fläche von © Visvalingam, M., und Whyatt, J. D. (1992)
- Link zum Artikel (einige links veröffentlicht, die hier und anderswo sind tot): Archiv.ist/Tzq2
- Aktualisiert, der link zu dem Artikel mit @Kit ein.
- Hier ein aktualisierter link: dieser Archive full-size-Versionen der Bilder (wenn Sie auf Sie klicken): web.archive.org/web/20130330164327/http://www2.dcs.hull.ac.uk/...
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Den Kern des Algorithmus ist die Rangfolge der Punkte, die von Ihrer Bedeutung. Bedeutung der Punkt wird approximiert durch seine wirksame Fläche.
Angenommen, Sie haben eliminiert den Punkt A und dann neu berechnet, die effektive Fläche Punkt B. Das neue Gebiet kann größer sein oder kleinere als der alte. Es kann kleiner sein, als die effektive Fläche A. Allerdings ist der Algorithmus noch Ansichten B deutlicher als bei A.
Den Zweck der
if- Klausel, um sicherzustellen, dass Punkt B ist wichtiger als Eine in die endgültige Liste aufgenommen, das ist alles.FWIW Mike Bostock, der Schöpfer der d3.js, schrieb eine enge javascript-Implementierung dieses Algorithmus (Visvalingam-Algorithmus).
function area(t) { return Math.abs((t[0][0] - t[1][0]) * (t[2][1] - t[1][1]) - (t[0][0] - t[1][0]) * (t[2][1] - t[1][1])); }. Dies führt zu falschen Vereinfachung der Küste (die gezeigten Ergebnisse sind schlimmer als Sie bekommen könnte). Auch die maximale Fläche sparen ist nutzlos in dieser Implementierung, da es iterativ.Ich war verwirrt von diesem zu, ging zurück und Lesen Sie den Artikel nochmals, und afaict es nicht benötigt, wenn Sie die Punkte entfernen, wie Sie gehen - aka, wenn Sie tun eine one-off-Vereinfachung mit einem festen Bereich Schwelle. afaict die javascript-Implementierung arbeitet auf diese Weise, so ist es eigentlich gar nicht brauchen, die 'if' - Anweisung (aber es hat es trotzdem, na ja).
Den 'if' - Anweisung ist benötigt, wenn Sie halten alle die Punkte in der Umgebung. In diesem Fall sind Sie die Speicherung der "wirksamen Fläche" mit jedem Punkt, so dass später Sie können die filter, vielleicht mit einem interaktiven Schieberegler für die Anzahl der Ausgangs-Punkte. Durch die Speicherung, die größere effektive Fläche, die Sie erhalten die richtige Reihenfolge.