c++ - 如何在多边形内构造 voronoi 图？

Question

我需要一种算法来填充一个二维非凸多边形，该多边形可能具有随机点的孔，然后在它们上构造一个 voronoi 图。该图应以多边形为界，算法应在 O(n log n) 内运行。

我的想法是通过测试多边形边界框内的随机点并仅取多边形内的点来填充多边形，而不是在其上构建 voronoi，而不是剪裁退出多边形的图的边缘。

问题是，测试随机点和裁剪边缘是 O(n^2)。

这可以在 boost 中完成，还是有另一个小型库，或者其他任何东西？

Answer 1

我想对于“孔”，您会遇到单个闭合多边形的自相交。

首先对多边形进行 Delaunay 三角剖分:

• 计算线段之间的截面点；添加这些点，拆分线段并重新排列输入，以便在遍历多边形的点时“内部”始终位于边缘的同一侧。
• 对多边形中的所有点进行剖分。
• 删除多边形之外的三角形。这些将是自相交产生的凹陷和孔洞。您可以通过沿着多边形行走并删除位于边缘之外的所有三角形来识别它们。您需要边缘的连通性，但这是三角测量的副产品。

您现在有了使用 Bowyer-Watson algorithm 进行进一步三角测量的起点, 它通过连续向父三角形添加点来进行三角剖分。因此，要添加一个随机点，我们可以选择一个点并一次性更新三角剖分:

• 随机选择一个三角形，其中每个三角形被选中的概率与其面积成正比。

• 通过选择 barycentric coordinates 在该三角形内选择一个随机位置s in [0, 1]，t in[0, 1]and withs + t < 1`。那么你的新观点是:

  {P} = s * ({N2} - {N1}) + t * ({N3} - {N1})
  

• 添加您的点并重新三角化父三角形和外接圆包含新点的其他三角形。

• 要选择的三角形集现在已经改变。

您现在有一个 Delaunay 三角剖分，但您需要一个 Voronoi 图，您可以通过连接相邻三角形的所有外接圆的中心轻松获得它。同样，Delaunay 三角剖分为您提供有关外接圆和哪些三角形相邻的信息。

当您创建一个包含所有点的大虚拟三角形时，您可以在初始三角测量中使用 Bowyer-Watson 算法。

我不知道有任何用于 C++ 的三角剖分库，但是 this question可能会让您入门。