algorithm - 查找具有区域约束的 Voronoi 镶嵌

Question

假设我们想要对具有 N 个点的矩形曲面进行 Voronoi 划分。Voronoi 镶嵌导致 N 个区域对应于 N 个点。对于每个区域，我们计算其面积并将其除以整个表面的总面积 - 称这些数字为 a1, ..., aN。它们的总和等于 1。

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

如何找到用于 Voronoi 划分的 N 个点的坐标选择(任意)，使得 a1==b1, a2==b2, ..., aN==bN？

编辑:

考虑一下之后，也许 Voronoi 分区不是最好的解决方案，重点是对表面进行随机不规则划分，以便 N 个区域具有适当的大小。 Voronoi 在我看来是合乎逻辑的选择，但我可能错了。

Answer 1

我会选择一些遗传算法。

基本流程如下:

1) 创建属于您的矩形的 100 组随机点。

2) 对于每个集合，计算 voronoï 图和面积

3) 对于每组，评估它与您预设的权重相比的好坏(称之为分数)

4) 按分数对点集进行排序

5) 丢弃最差的 50 个集合

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

7) 跳到第 2 步，直到满足条件(分数高于阈值、出现次数、花费的时间等...)

你最终会(希望)得到一个“有点合适”的结果。