Minimieren Polygon-Scheitel

Question

Was ist ein guter Algorithmus, um die Anzahl der Ecken in einem Polygon zur Reduktion, ohne die Art und Weise ändert es sehr viel aussieht?

Input: Ein Polygon, als eine Liste von Punkten dargestellt, mit viel zu vielen verticies: roh Eingabe von der Maus, zum Beispiel

.

Ausgang: Ein Polygon mit viel weniger verticies, die noch viel wie das Original aussieht: etwas Brauchbares für die Kollisionserkennung, beispielsweise (nicht notwendigerweise konvex)

.

Edit: Die Lösung hierfür wäre eine mehr segmentierte Linie der besten Anpassung in einem Diagramm zu finden, ähnlich sein. Es ist in meinem Buch Algorithmen Segmented Least Squares genannt wird.

Edit2:. Der Douglas Peucker Algorithmus ist, was ich will wirklich

Answer 1

Edit: Oh look, Simplifying Polygonen

Sie haben erwähnt, Kollisionserkennung. Man könnte wirklich einfach gehen und einen Begrenzungs konvexe Hülle um ihn herum zu berechnen.

Wenn Sie sich über den konkaven Flächen gepflegt, können Sie einen konkaven Rumpf berechnen, indem Sie den Schwerpunkt Ihrer Polygon nehmen, und einen Punkt der Wahl zu starten. Vom Ausgangspunkt dreht um den Schwerpunkt, findet jede Ecke Sie behalten mögen, und Zuweisen dass als nächsten Scheitelpunkt in dem begrenzenden Rumpf. Die Komplexität des Algorithmus kommen würde, wie Sie bestimmt, welche zu halten Scheitelpunkte, aber ich bin sicher, dass Sie schon daran gedacht. Sie können alle Ecken in Eimern auf der Grundlage ihrer Position in Bezug auf den Schwerpunkt werfen. Wenn ein Eimer mehr als eine beliebige Anzahl von Eckpunkten voll ist, können Sie es geteilt. Dann nehmen Sie den Mittelwert der Eckpunkt in diesem Eimer als Scheitelpunkt in der begrenzenden Rumpf zu verwenden. Oder vergessen die Eimer, und wenn man um den Schwerpunkt in Bewegung sind, wählen Sie nur einen Punkt, wenn seine mehr als einen bestimmten Abstand vom letzten Punkt.

Eigentlich könnte man wahrscheinlich alle Ecken in Ihrem Polygon als „Punktwolke“ verwenden Sie einfach und berechnet den konkaven Rumpf um die. Ich werde für einen Algorithmus Link suchen. Im schlimmsten Fall dazu wäre ein völlig konvexer Polygon sein.

Eine weitere Alternative ist mit einem Begrenzungsrechteck zu starten. Für jede Ecke auf das Rechteck, finden Sie den Abstand von dem Punkt auf dem Polygon. Für den am weitesten entfernten Scheitel, spaltete es in zwei weitere Ecken und sie in ein paar bewegen. Wiederholen, bis ein gewisser Anteil von entweder Ecken oder Bereich erfüllt ist. Ich würde ein wenig mehr über die Details dieses denken.

Wenn Sie kümmern sich um das Polygon tatsächlich auf der Suche ähnlich, auch im Fall eines selbstschneidendes Polygon, dann wäre ein anderer Ansatz erforderlich sein, aber es klingt nicht wie das ist notwendig, da Sie Kollisionserkennung gefragt.

Die Post hat einige Details über den konvexen Rumpfteil.

Answer 2

Es gibt eine Menge Material gibt. Gerade Google für Dinge wie "Mesh-Reduktion", "Mesh Vereinfachung", "Mesh-Optimierung", etc.