algorithm - 将 voronoi 边转换为多边形

Question

目前我正在尝试让 Voronoi 多边形划分一定大小的平面（例如 1000x1000 和 500 个随机点）。

为此，我使用了 Delaunay 的三角测量 - Bowyer Watson 算法。多亏了这一点，我能够生成点并正确连接 Voronoi 图中包含的边。不幸的是，就我而言，我需要一个多边形列表（其中每个多边形都包含一个边缘列表）。

我试图创建一个简单的算法，该算法将一个接一个地获取边缘并寻找下一个以创建最终多边形等等 - 不幸的是没有成功。我也在考虑取三角形的顶点并创建一个圆，直到形成多边形（从现有的边缘），但我不确定这是否是一个好的解决方案？

有什么办法吗？或者我应该使用不同的算法来获取 Voronoi 多边形列表？我在网上没有找到适合这个问题的解决方案，如果有的话，我将不胜感激链接

标签： algorithmgraph-theoryvoronoi

Answer 1

• 选择 E 任意边
• 将 E 中的顶点添加到多边形
• 选择点 P 稍微靠近 E 的一侧
• 如果点在平面内
  • 选择选定边的一个顶点
  • 从与点 P 边上角度最小的顶点选择 E2 新边
  • 将 E2 中的第二个顶点添加到多边形
  • 重复最后两个步骤，直到到达 E 中的其他顶点
  • 将多边形添加到解决方案（如果尚未包含）
• 用边缘另一侧的点重复
• 重复直到处理完所有边缘