假设我有一个固定的点数（X），例如，在给定平面内的坐标（我认为你可以称之为二维点云）。如何划分飞机
这些点应划分为Y多边形，其中Y < X.多边形不应该重叠。如果多边形是konvex（如Voronoi图），那将会很棒。
想象它就像形成国家的地点。例如，我有12个点，并且想要创建3个多边形，每个点有4个点。
我想过创建一个覆盖点的网格。然后遍历这些点，将它们分配给最近的网格单元格。
也许我想念明显？我相信有更好的解决方案。
感谢， 丹尼尔
我刚刚发现an optimization (kmeans++)。也许这会产生更好的结果..
你提到的Voronoi图，你看了相关tesselation algorithms？如果是这样，你能强调他们为什么不为你工作吗？
Voronoi图每个多边形都有一个点，但是这里应该有多个点组成多边形。我忘了提及：我也尝试了劳埃德算法（k-means），但是结果依赖于最初的选择。收敛性通常不太好。 – puls200 2009-08-12 08:27:53
您可能需要更好地定义您希望用来创建多边形分区的条件。例如，如果它是邻近的，则可以执行以下操作;
如果它是每个多边形点的数量相等的期望数量，你可以这样做基于合并相邻多边形，直到满足所需的点数为止。
编辑：如果凸性是最重要的问题，您可以简单地在云中间取一个点，并将径向投影到边缘以将云分成径向的三角形阵列。
可能是有用的2D Polygon Partitioning
http://www.cs.sunysb.edu/~algorith/files/polygon-partitioning.shtml – Alin 2009-08-12 09:31:44
具一格，你可能会得到空细胞，或所有的点在一个单元格。使用径向阵列，您可以用快速且易于实施的解决方案来克服这一问题。 – 2009-08-12 08:56:31