有人可以向我指出如何构建（乘法和/或加法）加权 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 可以做到这一点。这也使得实现变得非常容易。
对于到中心的距离用乘法因子加权的情况，几乎没有“现成的”开源代码。据我所知，当前的 CGAL 包都没有涵盖这种情况。
Takashi Ohyama 色彩绚丽的网站提供了 java 实现 http://www.nirarebakun.com/voro/emwvoro.html ，使用简单算法（欧几里得距离和曼哈顿距离）最多可以得到 100 个点。还有一篇论文描述了这种简单的交集算法和 O(n^3) 时间内的近似实现，作为 TerraView 的插件。但是，我在 TerraView / TerraLib 存储库中找不到此插件的来源： http ://www.geoinfo.info/geoinfo2011/papers/mauricio1.pdf
Aurenhammer 和 Edelsbrunner 描述了一个最佳的 n^2 时间算法，但我不知道可用的代码。
