0

假设我有一个固定数量 (X) 的点，例如给定平面内的坐标（我认为您可以将其称为二维点云）。

这些点应划分为 Y < X 的 Y 多边形。多边形不应重叠。如果多边形是凸多边形（如 Voronoi 图），那就太好了。

把它想象成形成国家的地点。例如，我有 12 个点，想创建 3 个多边形，每个多边形有 4 个点。

我考虑过创建一个覆盖点的网格。然后遍历这些点，将它们分配给最近的网格单元。

也许我错过了显而易见的事情？我相信有更好的解决方案。

谢谢，丹尼尔

我刚刚找到了一个优化（kmeans++）。也许这会产生更好的结果..

4

3 回答 3

1

你提到了Voronoi图，你看过相关的镶嵌算法吗？如果是这样，您能否强调为什么它们不适合您？

于 2009-08-12T08:12:50.450 回答
0

您可能需要更好地定义要用于创建多边形分区的标准。例如，如果它是邻近的，您可以执行以下操作；

  • 构建一个 voronoi 图。
  • 如果任何两个相邻的多边形有近邻，则将它们合并为一个多边形
  • 重复直到获得所需数量的多边形

如果每个多边形的点数相等，您可以基于合并相邻多边形来做类似的事情，直到满足所需的点数。

编辑：如果凸度是最重要的问题，您可以简单地在云中间取一个点并将径向投影到边缘以将云划分为三角形的径向阵列。

于 2009-08-12T08:21:54.427 回答
0

可能有用的2D 多边形分区

于 2009-08-12T09:25:25.343 回答