c++ - 给定一组点，通过voroni逼近将空间分割为多边形区域

我试图将空间划分为一组多边形，其中每个多边形对于一组输入点中的一个近似为一个voroni单元。

我试图为此使用Boost :: Voroni，但是使用此库的输出很复杂，需要大量额外的精力才能得到我想要的。

我想知道是否有人知道从BOOST :: voroni图中获取我想要的东西的最佳方法，还是有人知道一个比直接获取我正在寻找的东西简单的库？

这是一些代码，显示我正在尝试做的事情，

voronoi_diagram< float > vd;
construct_voronoi( gridPointPos.begin(), gridPointPos.end(), &vd );

int index = 0;
for (voronoi_diagram<float>::const_cell_iterator it = vd.cells().begin();
    it != vd.cells().end(); ++it, ++index ) {

    // if the voroni cell has infinite edges,
        // then clip them to a finite length

    // extract the voroni vertices of this cell

    // create a boost polygon from the extracted edges
}

因为boost对于我的需求来说过于笼统和复杂，所以我更喜欢一个库或算法来完成所有这些工作，只返回多边形集。我有什么选择？

最佳答案

您可以尝试用Bowyer-Watson增量算法实现PHP中的delaunay三角剖分，它还会发现voronoi图。您可以从codeplex.com（http://voronoi.codeplex.com/）下载它。