algorithm - 加权 voronoi 图的引用算法？

Question

谁能给我指出一个关于如何构建(乘法和/或加法)加权 voronoi 图的引用实现，该图最好基于 Fortune 的 voronoi 算法？

我的目标:给定一组点(每个点都有一个权重)和一组边界边(通常是一个矩形)我想使用 python 或 processing.org-framework 构建一个加权的 voronoi 图。这是一个 example .

到目前为止我所做的工作:到目前为止，我已经实现了 Fortune 的算法以及 Michael Balzer's paper 中介绍的“质心 voronoi 镶嵌”。 .算法 3 说明了需要如何调整权重，但是，当我实现它时，我的几何图形不再起作用。要解决此问题，必须更新扫描线算法以考虑权重，但到目前为止我无法做到这一点。因此，我想看看其他人是如何解决这个问题的。

Answer 1

对于附加加权的 Voronoi 图:Remember that a power diagram in dimension n is only a(n unweighted) Voronoi diagram in dimension n+1 .

为此，只需回想一下，如果向坐标添加任何常数，则点集的 Voronoi 图是不变的，因此加权 Voronoi 图可以使用坐标写成非加权 Voronoi 图，例如2D 提升为 3D:
(x_i, y_i, sqrt(C - w_i))
其中 w_i 是种子的权重，C 是任意大的常数(在实践中，一个刚好小到 C-w_i 为正的常数)。
计算图表后，只需丢弃最后一个组件。

因此，基本上，与您的问题相比，您只需要找到一个能够处理维度 n+1 中的 Voronoi 图的库。 CGAL 可以做到这一点。这也使实现变得非常容易。