假设我们想要对一个具有 N 个点的矩形表面进行 Voronoi 分区。Voronoi 细分导致 N 个区域对应于 N 个点。对于每个区域，我们计算其面积并将其除以整个表面的总面积 - 称这些数字为 a1，...，aN。它们的总和等于一。
假设现在我们有 N 个数字的预设列表，b1，...，bN，它们的总和等于 1。
如何找到用于 Voronoi 分区的 N 个点的坐标的选择（任意），例如 a1==b1、a2==b2、...、aN==bN？
编辑：
经过一番思考，Voronoi 分区可能不是最好的解决方案，关键是要对表面进行随机不规则划分，以使 N 个区域具有适当的大小。Voronoi 在我看来是合乎逻辑的选择，但我可能弄错了。
我会去一些遗传算法。
以下是基本流程：
1) 创建 100 组属于您的矩形的随机点。
2) 对于每个集合，计算 voronoï 图和面积
3) 对于每组，评估它与您的预设权重的比较情况（称之为分数）
4) 按分数对点集进行排序
5) 丢弃 50 个最差的集合
6）通过mixins点从剩余的50个集合中创建50个新集合并添加一些随机的。
7) 跳转到第 2 步，直到满足条件（得分高于阈值、出现次数、花费时间等...）
你最终会（希望）得到一个“有点合适”的结果。
如果您要查找的不一定是 Voronoi 镶嵌，而可能是幂图，则以下文章中描述了一个不错的算法：
F. Aurenhammer、F. Hoffmann 和 B. Aronov，“Minkowski 型定理和最小二乘聚类”， Algorithmica，20 :61-76 (1998)。
他们的问题版本如下：给定多边形 P 中的 N 个点 (p_i)，以及一组非负实数 (a_i) 与 P 的面积相加，求权重 (w_i)，使得Power cell Pow_w(p_i) 与 P 的交集正好是 a_i。在论文的第 5 节中，他们证明了这个问题可以写成凸优化问题。要实施这种方法，您需要：
我的网页上有一些代码正是这样做的，名称为“二次最优传输”。然而，这段代码不是很干净，也不是很好的文档，所以实现你自己的算法版本可能会一样快。您还可以查看我关于此主题的 SGP2011 论文，该论文可在同一页面上找到，以简要描述 Aurenhammer、Hoffman 和 Aronov 算法的实现。
假设矩形与 x = 0 处的左边缘和 x = 1 处的右边缘以及 y = 0 处的水平平分线轴对齐的坐标。令 B(0) = 0 和 B(i) = b1 + ... +双。将点放在 ((B(i-1) + B(i))/2, 0) 处。这是不对的。我们将 x 坐标设为 xi，使得 bi = (x(i+1) - x(i-1)) / 2，将 x(0) 替换为 0，将 x(n+1) 替换为 1。这是三对角线和应该有一个简单的解决方案，但也许你不想要这么无聊的 Voronoi 图；这将是一堆垂直分区。
对于一个看起来更随机的图，可能是受到了物理学启发：随机放置点，计算 Voronoi 图，计算每个单元格的面积，使超重单元格对其邻居的点有吸引力，而体重不足的单元格排斥并为每个单元格计算一个小的增量点，重复直到达到平衡。
当您计算最小生成树并移除最长边时，可以计算 voronoi 镶嵌。然后，mst 子树的每个中心都是 voronoi 图的一个点。因此，voronoi 图是最小生成树的子集。