Minimieren von Polygonscheitelpunkten

Question

Was ist ein guter Algorithmus zum Reduzieren der Anzahl von Scheitelpunkten in einem Polygon, ohne die Darstellung stark zu verändern?

Eingabe: Ein Polygon, dargestellt als eine Liste von Punkten, mit viel zu vielen Vertices: rohe Eingabe von der Maus, zum Beispiel.

Ausgabe: Ein Polygon mit viel weniger Vertices, das dem Original immer noch sehr ähnlich ist: etwas, das beispielsweise für die Kollisionserkennung geeignet ist (nicht notwendigerweise konvex).

Edit: Die Lösung hierfür wäre vergleichbar mit der Suche nach einer mehrsegmentierten Linie mit der besten Anpassung auf einem Graphen. Es heißt Segmented Least Squares in meinem Algorithmenbuch.

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

Answer 1

Edit: Oh look, Simplifying Polygons

Sie erwähnten Kollisionserkennung. Sie könnten wirklich einfach gehen und eine umgebende konvexe Hülle um sie herum berechnen.

Wenn Sie sich für die konkaven Bereiche interessiert haben, können Sie eine konkave Hülle berechnen, indem Sie den Schwerpunkt Ihres Polygons nehmen und einen Startpunkt auswählen. Vom Startpunkt aus rotieren Sie um den Schwerpunkt herum, finden jeden Eckpunkt, den Sie behalten möchten, und ordnen ihn dem nächsten Eckpunkt in der Begrenzungshülle zu. Die Komplexität des Algorithmus würde darin liegen, wie Sie bestimmt haben, welche Scheitelpunkte Sie behalten möchten, aber ich bin mir sicher, dass Sie schon darüber nachgedacht haben. Sie können alle Ihre Scheitelpunkte basierend auf ihrer Position relativ zum Schwerpunkt in Buckets werfen. Wenn ein Bucket mehr als eine beliebige Anzahl von Scheitelpunkten voll hat, können Sie es teilen. Dann nehmen Sie den Mittelwert der Scheitelpunkte in diesem Bucket als den Scheitelpunkt, der in Ihrer umgebenden Hülle verwendet werden soll. Oder, vergessen Sie die Eimer, und wenn Sie sich um den Schwerpunkt bewegen, wählen Sie nur einen Punkt, wenn er mehr als eine bestimmte Entfernung vom letzten Punkt entfernt ist.

Eigentlich könnten Sie wahrscheinlich alle Eckpunkte in Ihrem Polygon als "Punktwolke" verwenden und die konkave Hülle um diese herum berechnen. Ich werde nach einem Algorithmus Link suchen. Im schlimmsten Fall wäre das ein komplett konvexes Polygon.

Eine andere Alternative besteht darin, mit einem Begrenzungsrechteck zu beginnen. Suchen Sie für jeden Eckpunkt des Rechtecks ​​den Abstand zwischen dem Punkt und dem Polygon. Für den am weitesten entfernten Eckpunkt teilen Sie ihn in zwei weitere Eckpunkte und verschieben Sie sie in einige. Wiederholen Sie diesen Vorgang, bis ein bestimmter Anteil der Scheitelpunkte oder Bereiche erreicht ist. Ich müsste noch ein bisschen mehr über die Details nachdenken.

Wenn das Polygon wirklich ähnlich aussieht, selbst im Falle eines sich selbst schneidenden Polygons, wäre ein anderer Ansatz erforderlich, aber es klingt nicht so, als ob Sie nach Kollisionserkennung gefragt hätten.

Diese post hat einige Details über den konvexen Rumpfteil.

Answer 2

Es gibt eine Menge Material da draußen. Gerade Google für Dinge wie "Mesh-Reduktion", "Mesh Vereinfachung", "Mesh-Optimierung" usw.