实现 Voronoi 图的简单算法有哪些？
我找不到任何专门以伪形式出现的算法。请分享一些 Voronoi 图算法、教程等链接。
计算点集 Delaunay 三角剖分的简单算法是翻转边缘 http://www.cise.ufl.edu/~ungor/delaunay/delaunay/node5.html。由于 Delaunay 三角剖分是 Voronoi 图的对偶图，因此您可以在线性时间内根据三角剖分构造该图。
不幸的是，翻转方法的最坏情况运行时间是 O(n^2)。存在更好的算法，例如 Fortune 的线扫描，它需要 O(n log n) 时间。但这实施起来有些棘手。如果您很懒（像我一样），我建议您寻找 Delaunay 三角剖分的现有实现，使用它，然后计算对偶图。
一般来说，关于该主题的一本好书是计算几何 https://rads.stackoverflow.com/amzn/click/com/3540779736德伯格等人。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
