我需要一种算法，它可以随机填充一个2D非凸多边形，该多边形可能有带点的孔，然后在其上构造一个voronoi图。图应以多边形为界，算法应在O(n log n)中运行。
我的想法是通过测试多边形边界框内的随机点来填充多边形，并且只取多边形内的点，然后在它们上构建voronoi，然后剪切退出多边形的图的边缘。
问题是，测试随机点并裁剪边缘是O(n^2)。
这可以在boost中完成吗，或者有另一个小库，或者其他什么?
我猜"孔"是指一个封闭多边形的自交点。
先对多边形进行Delaunay三角剖分:
- 计算段间的截面点;添加这些点，分割片段并重新排列输入，以便"inside"在遍历多边形点时始终位于边缘的同一侧。
- 将多边形中的所有点三角形化
- 删除位于多边形外的三角形。这些将是由自交产生的凹坑和洞。您可以通过沿着多边形行走并删除位于边缘外的所有三角形来识别它们。你需要边的连通性，但这是三角测量的副产品。
您现在已经有了使用Bowyer-Watson算法进行进一步三角测量的起点，该算法通过连续向父三角形添加点来进行三角测量。因此，为了添加一个随机点，我们可以选择一个点并一次更新三角测量:
- 选择一个随机三角形，其中每个三角形被选中的概率与其面积成正比。
-
通过选取质心坐标
s in [0, 1],t in[0,1]and withs + t <1"。你的新观点是:{P} = s * ({N2} - {N1}) + t * ({N3} - {N1}) -
添加你的点并重新测量父三角形和其他圆形包含新点的三角形
- 选择三角形的集合现在已经改变了。
你现在有了一个Delaunay三角剖分，但你想要一个Voronoi图，你可以很容易地通过连接相邻三角形的所有圆的中心来获得。同样，德劳内三角剖分法为您提供了有关圆的信息以及哪些三角形相邻。
当你创建一个包含所有点的大虚拟三角形时，你可以在初始三角测量中使用Bowyer-Watson算法。
我不知道c++中有任何三角测量库，但这个问题可能会让你开始。