Vereinfachte (oder glatte) Polygone, die das ursprüngliche detaillierte Polygon enthalten
Habe ich eine detaillierte 2D-polygon " (die ein geographisches Gebiet), die definiert ist durch eine sehr große Menge von vertices. Ich bin auf der Suche nach einem Algorithmus, zu vereinfachen und glätten die polygon (Reduzierung der Anzahl der Eckpunkte) mit der Einschränkung, dass das Bereich des resultierenden Polygons enthält alle Eckpunkte der detaillierten polygon.
Kontext, hier ein Beispiel von der Kante eines komplexen Polygons:
Meiner Forschung:
- Fand ich den Ramer–Douglas–Peucker-Algorithmus, die eine Verringerung der Anzahl der Scheitelpunkte - aber das resultierende polygon wird nicht alle von den ursprünglichen polygon-Eckpunkte. Finden Sie in diesem Artikel Ramer-Douglas-Peucker bei Wikipedia
- Ich als Erweiterung des Polygons (ich glaube, dies ist auch bekannt als die äußeren polygon offsetting). Ich fand diese Fragen: Erweitern ein polygon (konvex nur) und Das aufblasen eines Polygons. Aber ich glaube nicht, dass dies erheblich reduzieren die detail meiner polygon.
Vielen Dank für jeden Rat können Sie mir geben!
InformationsquelleAutor der Frage mbrenig | 2011-02-18
Schreibe einen Kommentar
Du musst angemeldet sein, um einen Kommentar abzugeben.
Bearbeiten
Als 2013, die meisten unten aufgeführten links sind nicht funktionsfähig nicht mehr. Ich finde jedoch,die zitierte Papier-Algorithmus enthalten, noch bei dieser (sehr langsamen) server.
Hier finden Sie ein Projekt, das sich genau mit deinen Fragen. Obwohl es in Erster Linie arbeitet mit einer Fläche "gefüllt", indem Sie Punkte, können Sie es zur Arbeit mit einer "Umfang" - Typ-definition wie deine.
Verwendet es eine k-nächste-Nachbarn Ansatz für die Berechnung der region.
Proben:
Hier Sie kann verlangen, eine Kopie des Papiers.
Scheinbar Sie geplant, bieten einen online-service für die Beantragung Berechnungen, aber ich habe nicht testen Sie es, und wahrscheinlich nicht laufen.
HTH!
InformationsquelleAutor der Antwort Dr. belisarius
Das ist ein Interessantes problem! Ich habe nie versucht, so etwas wie dieses, aber hier ist eine Idee aus der Spitze von meinem Kopf... entschuldigt, wenn es keinen Sinn macht, oder würde das nicht funktionieren 🙂
Jeder Ebene der Rekursion sollte eine bessere Näherung.... wenn Sie erreicht ein befriedigendes Niveau, verbindet alle der Rümpfe aus, dass die Ebene, um das Letzte polygon.
Klingt wie es könnte den job machen?
InformationsquelleAutor der Antwort Gromix
Ich hatte ein sehr ähnliches problem : ich brauchte ein aufblasen Vereinfachung von Polygonen.
Ich habe einen einfachen Algorithmus, durch entfernen concav Punkt (dadurch erhöht sich die polygon-Größe) oder entfernen von konvexen Kante (zwischen 2 konvexe Punkte) und prolongating angrenzenden Kanten. In jedem Fall, tun eine dieser 2 Möglichkeiten wird entfernen Sie einen Punkt auf dem polygon.
Wählte ich entfernt den Punkt oder die Kante, führt zu kleinsten Bereich variation. Sie können diesen Vorgang wiederholen, bis die Vereinfachung ist ok für Sie (zum Beispiel nicht mehr als 200 Punkte).
Den 2 größten Schwierigkeiten waren zu erhalten schneller Algorithmus (durch die Vermeidung von zu compute vertex/edge-removal-Variante doppelt und Aufrechterhaltung der Möglichkeiten sortiert) und vermeiden Sie das einlegen selbst-Kreuzung in den Prozess (nicht sehr einfach zu tun und zu erklären, aber möglich, mit begrenztem Rechenaufwand).
In der Tat, nach einem Blick mehr eng, es ist eine ähnliche Idee, als die, die man von Visvalingam mit Anpassung für Rand entfernen.
InformationsquelleAutor der Antwort Renaud
Bis zu einem gewissen Grad bin ich mir nicht sicher, was Sie versuchen zu tun, aber es scheint, Sie haben zwei sehr gute Antworten. Man Ramer–Douglas–Peucker (DP) und der andere ist der Berechnung der alpha-Form (auch als kugeliger Rumpf, nicht-konvexe Hülle, etc.). Ich fand eine neuere Papier beschreibt alpha-Formen und verknüpft Sie unten.
Ich persönlich denke, dass DP mit polygon-Erweiterung ist der Weg zu gehen. Ich bin mir nicht sicher, warum Sie denken, es wird nicht deutlich reduzieren Sie die Anzahl der Scheitelpunkte. Mit DP, die Sie liefern, ein Faktor, und Sie können machen, was Sie wollen zu dem Punkt, wo Sie am Ende ein Dreieck, egal, was Sie Ihre Eingabe. Die Kommissionierung dieser Faktor kann hart sein, aber in deinem Fall denke ich ist es die beste Methode. Sie sollten in der Lage sein zu bestimmen, der Faktor basiert auf der Größe der größten bit der Details, die Sie wollen, Weg zu gehen. Sie können dies tun, mit direkte Prüfungen oder durch Berechnung aus Ihren Quelldaten.
http://www.it.uu.se/edu/course/homepage/projektTDB/ht13/project10/Project-10-report.pdf
InformationsquelleAutor der Antwort Greg Breland
Ich denke Visvalingam-Algorithmus angepasst werden kann für diesen Zweck - durch überspringen entfernen von Dreiecken, würde Verringerung der Fläche.
InformationsquelleAutor der Antwort Juozas Kontvainis