How to partition a plane

Question

Let's say I have a fixed number (X) of points, e.g. coordinates within a given plane (I think you can call it a 2-D point cloud).

These points should be partitioned into Y polygons where Y < X. The polygons should not overlap. It would be wonderful if the polygons were konvex (like a Voronoi diagram).

Imagine it like locations forming countries. For example, I have 12 points and want to create 3 polygons with 4 points each.

I thought about creating a grid which covers the points. Then iterate across the points, assigning them to the closest grid cells.

Maybe I miss the obvious? I am sure there are better solutions.

Thanks, Daniel

I just found an optimization (kmeans++) .Maybe this will yield better results..

Answer 1

You probably need to better define what criteria you wish to use to create your polygonal partitions. For example, if it is proximity, you could do the following;

• Construct a voronoi diagram.
• Where any two adjacent polygons have a close neighbour, merge them into a single polygon
• Repeat until you have the desired number of polygons

If it was equal number of points per polygon, you could do something similar based on merging adjacent polygons with until a desired point count is met.

Edit: If convexity was the most important issue, you could simply take a point in the middle of you cloud and project radials to the edge to divide the cloud into a radial array of triangles.

Answer 2

Might be useful 2D Polygon Partitioning