So partitionieren Sie eine Ebene

Question

Nehmen wir an, ich habe eine feste Anzahl (X) von Punkten, z. Koordinaten innerhalb einer gegebenen Ebene (ich denke, Sie können es eine 2-D Punktwolke nennen).

Diese Punkte sollten in Y Polygone aufgeteilt werden, wobei Y < X. Die Polygone sollten nicht überlappen. Es wäre wunderbar, wenn die Polygone konvex wären (wie ein Voronoi-Diagramm).

Stellen Sie sich vor Orte wie Länder bilden. Zum Beispiel habe ich 12 Punkte und möchte 3 Polygone mit jeweils 4 Punkten erstellen.

Ich dachte über das Erstellen eines Gitters, das die Punkte abdeckt. Dann iteriere über die Punkte und weise sie den nächsten Gitterzellen zu.

Vielleicht vermisse ich das Offensichtliche? Ich bin mir sicher, dass es bessere Lösungen gibt.

Danke, Daniel

Ich habe gerade an optimization (kmeans++) .maybe dies bessere Ergebnisse bringen wird ..

Answer 1

Sie die Voronoidiagramm erwähnen, haben Sie bei der entsprechenden tesselation algorithms geschaut? Wenn ja, könnten Sie betonen, warum sie nicht für Sie arbeiten?

Answer 2

Sie müssen wahrscheinlich besser definieren, welche Kriterien Sie zum Erstellen Ihrer polygonalen Partitionen verwenden möchten. Zum Beispiel, wenn es Nähe ist, könnten Sie Folgendes tun:

• Konstruieren Sie ein Voronoi-Diagramm.
• Wo zwei benachbarte Polygone, die einen nahen Nachbarn haben, verschmelzen sie zu einem einzigen Polygon
• wiederholen, bis die gewünschte Anzahl von Polygonen

Wenn es die gleiche Anzahl von Punkten pro Polygon haben, die Sie tun können etwas Ähnliches basierend auf dem Zusammenführen benachbarter Polygone, bis eine gewünschte Punktzahl erreicht ist.

Bearbeiten: Wenn Konvexität das wichtigste Problem war, könnten Sie einfach einen Punkt in der Mitte der Wolke nehmen und Radiale an den Rand projizieren, um die Wolke in eine radiale Anordnung von Dreiecken zu unterteilen.

Answer 3

Might 2D Polygon Partitioning