寻找带有面积约束的Voronoi图分割。

Question

寻找带有面积约束的Voronoi图分割。

algorithmcomputational-geometryvoronoi

3

假设我们想用N个点将一个矩形表面进行 Voronoi 分割。Voronoi 镶嵌结果得到 N 个区域，对应于 N 个点。对于每个区域，我们计算其面积并将其除以整个表面的总面积 - 将这些数字称为 a1, ..., aN。它们的总和等于一。

现在假设我们有一个预设的 N 个数字列表，b1, ..., bN，它们的总和等于一。

如何才能找到一组坐标来进行 Voronoi 分割，使得 a1==b1，a2==b2，...，aN==bN？

编辑：

经过一番思考，也许 Voronoi 分割并不是最佳解决方案，整个问题在于提出随机不规则分割表面的方法，使得 N 个区域具有适当的大小。对我而言，Voronoi 看起来像是一个合乎逻辑的选择，但我可能错了。

- vedran

你是在寻找精确匹配吗？如果不是，我会用一些遗传算法。 - Nicolas Repiquet

好的，“几乎” 精确就足够了。唉，我不熟悉遗传算法，但还是谢谢你的指引！ - vedran

为什么你想要一个* Voronoi *镶嵌？从答案/评论中听起来，更像是你想要一个带有一些面积限制的不规则/吸引人的分割。如果是这样的话，你应该明确说明... - andrew cooke

嗯，我有点被Voronoi分割弄糊涂了，似乎是最简单的实现方式。你有什么特别的想法可以更合适吗？ - vedran

4个回答

2

如果你寻找的不一定是 Voronoi 图案，而可以是 Power 图案，那么可以参考以下文章中描述的一个好的算法：

F. Aurenhammer, F. Hoffmann, and B. Aronov, "Minkowski-type theorems and least-squares clustering," Algorithmica, 20:61-76 (1998).

他们的问题版本如下：给定多边形 P 中的 N 个点 (p_i) 和一组非负实数 (a_i)，其总和为 P 的面积，找到权重 (w_i)，使得 Power cell Pow_w(p_i) 与 P 的交集的面积恰好为 a_i。在论文的第五节中，他们证明了这个问题可以被写成一个凸优化问题。要实现这种方法，你需要：

- 能够高效计算 Power 图案的软件，例如 CGAL - 凸优化的软件。我发现使用拟牛顿求解器（如 L-BFGS）在实践中能够得到非常好的结果。

我在我的网页上有一些代码，可以完美地实现这个功能，名字叫做“二次优化运输”。但是这段代码并不十分规范，也没有很好的文档说明，所以你自己实现算法可能会更快。你也可以阅读我关于这个主题的 SGP2011 论文，在同一页中获得对Aurenhammer、Hoffman和Aronov算法实现的简短描述。

- Quentin M.

我稍微研究了一下，但是我很难读懂这篇论文。不过这个想法似乎不错，我可能会实现它。谢谢！ - vedran

1

假设矩形的坐标系是左边缘在x = 0，右边缘在x = 1，水平分隔线在y = 0。我们将B(0) = 0和B(i) = b1 + ... + bi。在((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图，计算每个单元格的面积，使超重单元格吸引其邻居的点，使轻量级单元格排斥并计算每个点的小增量，重复直到达到平衡状态。

- uty

所以，你所有的点都会在一条线上，所有的区域都是方框。聪明！即使我不认为这是 OP 寻找的 :) - Nicolas Repiquet

呵呵，好主意，当然！但是，我想生成随机镶嵌图案。比如，随机放置一些点，然后通过某种算法得出有效的分区。我肯定不想要这种退化情况。 :) - vedran

但这是您要求的内容！ - andrew cooke

0

在计算最小生成树并移除最长的边时，可以计算出Voronoi图。MST子树的每个中心点都是Voronoi图的一个点。因此，Voronoi图是最小生成树的一个子集。

- Micromega

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nicolas Repiquet · Accepted Answer

我会选择一些遗传算法。

以下是基本流程：

1）创建100个随机点集，这些点属于您的矩形范围。

2）对于每个点集，计算其Voronoï图和面积。

3）对于每个点集，评估其与预设权重的相似度（称为其得分）。

4）按得分对点集进行排序。

5）删除50个最差的点集。

6）通过混合点并添加一些随机点来从50个剩余的点集中创建50个新的点集。

7）跳转到步骤2，直到满足某种条件（得分高于阈值，出现次数，花费时间等等）。

最终会获得一个“较为合适”的结果。