我需要一种将一维值范围（即连续整数）随机分成 k 部分的方法。从技术上讲，只需使用伪随机生成器来选择分割点就可以完成工作。然而，它允许范围非常小（相反非常大）的可能性。我一直在寻找一种方法来解决这个问题，而无需使用硬编码的范围限制。
我找到了这篇文章。它与二维地形生成有关。但它面临同样的问题并提出了解决方案。您可以查看 Polygons 部分，其中作者提到了 Lloyd 松弛。整个事情的来源是 Voronoi 图，它适用于 2d 范围。此外，如果您查看构建 Lloyd 松弛所需的 Voronoi 图的算法，它的开头是：
令 *(z) 为变换 *(z) = (zx, zy + d(z))，其中 d(z) 是在 z 处最小值的抛物线
自然，我在 1d 中没有抛物线。
我不清楚如何在我的 1d 范围的情况下获得相同的结果。或者也许有一个不同/更好的方法来解决这个问题？
我没有深入了解他的代码的细节，但是他在 2d 中对 Voronoi 图所做的，然后选择多边形的中心作为新点并重新制作 Voronoi 图给了我这个想法：
1. Randomly select your points
2. Compute midways between your points
-> The two midways on the two sides of each point, is like
its Voronoi polygon in the Voronoi diagram
-> So let's call the range between these two "midways" a Voronoi range!
3. Replace each point by the center of its Voronoi range
4. If you want the values to be less random, loop back to step 2
5. The ranges you are looking for are the Voronoi ranges of the last results.
让我们举个例子。为简单起见，假设我们正在处理连续范围。
所以你从范围 [0, 80] 开始，你想把它分成 15 个范围。
假设您排序后的 15 个随机数是（由 C 程序生成：）
1 5 12 17 19 21 26 31 38 47 52 54 56 67 71
中点是：
1 5 12 17 19 21 26 31 38 47 52 54 56 67 71
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | |
3 8.5 14.5 18 20 23.5 28.5 34.5 42.5 49.5 51 55 61.5 69
所以你的范围变成：
[0, 3], [3, 8.5], [8.5, 14.5], [14.5, 18], [18, 20],
[20, 23.5], [23.5, 28.5], [28.5, 34.5], [34.5, 42.5], [42.5, 49.5],
[49.5, 51], [51, 55], [55, 61.5], [61.5, 69], [69, 80]
如果您想将其可视化，它看起来像这样（最好我可以在文本中显示它）：
+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+
其中.显示数字从 0 到 80 并+显示 Voronoi 范围的边缘。
现在，让我们应用第 3 步。
1 5 12 17 19 21 26 31 38 47 52 54 56 67 71
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | |
0 3 8.5 14.5 18 20 23.5 28.5 34.5 42.5 49.5 51 55 61.5 69 80
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | | |
1.5 | 11.5 16.25 19 21.75 26 31.5 38.5 46 50.25 53 58.25 65.25|
5.75 74.5
现在让我们看看新点的 Voronoi 范围如何：
1.5 5.75 11.5 16.25 19 21.75 26 31.5 38.5 46 50.25 53 58.25 65.25 74.5
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
| | | | | | | | | | | | | |
3.625 8.625 13.875 17.625| 23.875 | 35 42.25 48.125 | 55.625 61.75 69.875
20.375 28.75 51.625
现在你的范围是（它开始看起来很难看，但请耐心等待）
[0, 3.625], [3.625, 8.625], [8.625, 13.875],
[13.875, 17.625], [17.625, 20.375], [20.375, 23.875],
[23.875, 28.75], [28.75, 35], [35, 42.25],
[42.25, 48.125], [48.125, 51.625], [51.625, 55.625],
[55.625, 61.75], [61.75, 69.875], [69.875, 80]
那么现在让我们来看看这个点的分布是怎样的：
+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+
现在让我们比较两个分布：
First one
|
V
+..+.....+.....+..+.+...+....+.....+.......+......++...+......+......+.........+
+...+....+....+...+..+..+....+.....+.......+....+...+...+.....+.......+........+
^
|
Second one
看起来更好，不是吗？这正是他在您发现的将 2d Voronoi 多边形应用于 1d 范围的文章中所做的。
（请原谅我的任何可能的计算错误）