algorithm - 简化的省份生成

我需要一些巧妙且相当简单的解决方案来解决我的问题 - 省份形状生成。
假设映射是矩阵 NxM。每个单元格由自然数表示。 0 表示该图块不属于任何省份。数字 1 表示它属于省 nr 1，nr 2 表示单元格属于省 nr 2...等等。

考虑这张 map ，它是 4x4:

这张 map 代表了 16 个不属于任何省份的图块。

这是包含 1 个省的 map :

这是大小为 5 的省份，id = 1。它没有邻居。

考虑3个省:

所以省 1 是 2 和 3 的邻居。省 3 只是 1 的邻居，省 2 只是 1 的邻居。还有 7 个不相关的图块。

我的问题是:我想在 map NxN 上生成 k 个省份。还有一些简单的规则:

有省的最大大小和省的最小大小(例如 min = 2，max = 10)

省的所有瓦片都应该连接(通过垂直或水平，但不是角)

无效省份示例(未连接):

不应该有飞地(省内的省)

形状应该是随机的

我试图通过洪水填充修改来实现它，但它有一些缺点。我会很高兴听到一些想法或任何帮助。 map 可以是 300x300 的 200 个省份或更多，所以它也应该是一些聪明的算法。

最佳答案

使用 Voronoi Diagrams

我认为这个不会生成所有可能的 map ，但会生成最“合理”的 map 。

Voronoi 图包括根据与选定点的接近程度划分平面。您可以在标题的维基百科链接中查看示例。

算法:

1) 选择一组大于或等于您想要的省份数量的随机点。如果您生成的比需要的多，您将保证有空白空间。

2)运行Voronoi算法(如果你有兴趣可以描述它，但在网上很容易找到)

3) 计算所得多边形的面积

4) 检查您是否有足够的面积，表面 >(所需的最小面积)。如果没有，请转到 1

5)如果您生成的随机点比所需的多，请从面积>(最小面积)的多边形中随机选择组成每个省的多边形集

6)检查您的多边形是否具有面积
7) 减少每个多边形的面积

虽然面积 > (最大面积)

查找多边形边界

从多边形边界删除一个随机点

顺便说一句，我在 Mathematica 中编写了这个程序来获得上面的图表:

 Clear["Global`*"];
 Needs["ComputationalGeometry`"];
 data2D = Table[{RandomReal[16], RandomReal[16]}, {10}]
 convexhull = ConvexHull[data2D]
 (delval = DelaunayTriangulation[data2D]) // Shallow[#, {5, 6}] &
 b1 = {{0, 0}, {16, 0}, {16, 16}, {0, 16}};
 {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull];
 Show[{Graphics[Join[{PointSize[Large]}, {Point@data2D}], Frame -> True]}]
 Show[{Graphics@Point[data2D],   DiagramPlot[data2D, diagvert1, diagval1]}]

我包含代码只是为了表明该算法易于使用正确的工具实现。

注意:算法描述没有提到你的区域是由正方形组成的......

HTH

关于algorithm - 简化的省份生成，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4068658/