简化省一代

Question

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

考虑这张地图,即4x4:

0000
0000
0000
0000

此地图代表16个不属于任何省份的图块.

这是包含1个省的地图:

0010
0111
0100
0000

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

考虑3个省:

1133
2100
2200
2000

所以省1是2和3的邻居.省3只是1的邻居,省2只是1的邻居.还有7个不相关的瓦片.

我的问题是:我想在地图NxN上生成k个省份.也有一些简单的规则:

• 省的最大尺寸和省的最小尺寸(例如,min = 2,max = 10)
• 省的所有瓷砖应该连接(垂直或水平,但不是角落)

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

1100
0000
0011
0000

• 不应该有飞地(省内省)
• 形状应该是随机的

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

Answer 1

使用Voronoi图

我认为这个不会生成所有可能的地图,但会与大多数"合理的"地图一起生成.

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

算法:

1)选择一组大于或等于所需省数的随机点.如果生成的数量超过需要,则可以保证空的空间.

2)运行Voronoi算法(如果您感兴趣,可以描述它,但在网络上很容易找到)

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

4)检查表面是否有足够的区域>(最小所需区域).如果没有,请转到1

5)如果您生成的随机点多于所需的随机点,则随机选择将构成每个省的多边形集与面积>(min area)的多边形集合

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