Mar*_*kov 11 algorithm geometry voronoi data-structures
有人能指出我如何构建(乘法和/或加法)加权voronoi图的参考实现,最好是基于Fortune的voronoi算法吗？
我的目标:给定一组点(每个点都有一个权重)和一组边界边(通常是一个矩形),我想用python或processing.org-framework构建一个加权的voronoi图.这是一个例子.
到目前为止我所做的工作:到目前为止,我已经实现了Fortune的算法以及Michael Balzer的论文中提出的"centroidal voronoi tessellation" .算法3说明了如何调整权重,但是,当我实现这个时,我的几何不再适用.要解决此问题,必须更新扫描线算法以考虑权重,但到目前为止我无法做到这一点.因此,我想看看其他人是如何解决这个问题的.
对于加性加权Voronoi图:请记住,维度n中的幂图仅是维度n + 1中的(n未加权)Voronoi图.
为此,请回想一下,如果向坐标添加任何常量,则点集的Voronoi图是不变的,并且加权Voronoi图因此可以使用坐标写为非加权Voronoi图,例如在2D中提升到3D :(
x_i,y_i,sqrt(C-w_i))
其中w_i是种子的权重,C是任意大的常数(实际上,一个足够小,使得C-w_i为正).
计算完图表后,只需丢弃最后一个组件.
因此,基本上,您只需要找到一个能够处理维度n + 1的Voronoi图表的库,与您的问题相比.CGAL可以做到这一点.这也使得实现非常容易.