Voronoi图

Question

我正在寻找一个来源(论文，论文，视频，书籍)的详细，易于理解，解释如何在C或C++中实现Voronoi driagram。我要寻找的输出是绘制一个信息:顶点的位置和边的连通性。

我知道我可能要求太多了，但编程不是我的研究领域，所以我遇到的许多方法对我来说都是模棱两可的。然而，我并不是在寻找一个库，而是在寻找一种可以自己编写代码的方法。

谢谢。

Answer 1

如果你是勇敢的，试着用“L.J. Guibas和J. Stolfi，Primitives来操作一般的细分和计算Voronoi图”。

对“边代数”的介绍是艰巨的(甚至可怕的)，对于标准的应用程序来说是非常必要的。但是，如果你把重点放在拓扑和几何原语(四边图表示，圆内测试)的实际实现上，那么分集和征服算法就会变得非常清晰。

如果使用精确的算法，该算法是防弹的，而且这种方法是强大的。作为副产品，它将同时生成Voronoi图和Delaunay三角剖分。