Comment partitionner un plan

Question

Disons que j'ai un nombre fixe (X) de points, par ex. coordonnées dans un plan donné (je pense que vous pouvez l'appeler un nuage de points en 2D).

Ces points doivent être divisés en polygones Y où Y < X. Les polygones ne doivent pas se chevaucher. Ce serait merveilleux si les polygones étaient konvex (comme un diagramme de Voronoï). Imaginez-le comme des lieux formant des pays. Par exemple, j'ai 12 points et je veux créer 3 polygones avec 4 points chacun. J'ai pensé à créer une grille qui couvre les points. Puis parcourez les points en les affectant aux cellules de la grille les plus proches.

Peut-être que je manque l'évidence? Je suis certain qu'il existe de meilleures solutions.

Merci, Daniel

Je viens de découvrir an optimization (kmeans++) .Maybe cela donnera de meilleurs résultats ..

Answer 1

Vous mentionnez le diagramme de Voronoï, avez-vous regardé la tesselation algorithms connexe? Si oui, pourriez-vous souligner pourquoi ils ne travaillent pas pour vous?

Answer 2

Vous aurez probablement besoin de mieux définir les critères que vous souhaitez utiliser pour créer vos partitions polygonales. Par exemple, si c'est la proximité, vous pouvez faire ce qui suit:

• Construire un diagramme de voronoï.
• Lorsque des deux polygones adjacents ont un proche voisin, les fusionner en un seul polygone
• Répétez jusqu'à ce que vous avez le nombre désiré de polygones

Si elle était le même nombre de points par polygone, vous pouvez faire quelque chose de similaire basé sur la fusion de polygones adjacents avec jusqu'à ce qu'un nombre de points souhaité soit atteint. Si la convexité était le problème le plus important, vous pourriez simplement prendre un point au milieu de votre nuage et projeter des radiales sur le bord pour diviser le nuage en un réseau radial de triangles.

Answer 3

peut être utile 2D Polygon Partitioning