Was ist ein guter Algorithmus, um die Anzahl der Scheitelpunkte in einem Polygon zu reduzieren, 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).
Bearbeiten: Die Lösung hierfür wäre vergleichbar mit dem Auffinden einer mehrfach segmentierten Linie mit der besten Anpassung an ein Diagramm. Es heißt Segmented Least Squares in meinem Algorithmenbuch.
Edit2: Der Douglas Peucker Algorithmus ist was ich wirklich will.
Bearbeiten: Oh, Polygone vereinfachen
Sie haben die Kollisionserkennung erwähnt. Sie könnten wirklich einfach gehen und eine umgebende konvexe Hülle um sie herum berechnen.
Wenn Sie sich um die konkaven Bereiche gekümmert 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.
Tatsächlich könnten Sie wahrscheinlich alle Eckpunkte in Ihrem Polygon als "Punktwolke" verwenden und die konkave Hülle darum 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 über die Details ein bisschen mehr nachdenken.
Wenn das Polygon wirklich ähnlich aussieht, ist selbst im Falle eines sich selbst schneidenden Polygons ein anderer Ansatz erforderlich, aber es klingt nicht so, als ob Sie nach der Kollisionserkennung gefragt hätten.
>Dieser Post enthält einige Details über den konvexen Hüllenteil.
Es gibt eine Menge Material da draußen. Einfach googeln für Dinge wie "Mesh-Reduktion", "Mesh-Vereinfachung", "Mesh-Optimierung", etc.