3

我需要一些聪明且相当简单的解决方案来解决我的问题 - 省份形状生成。假设该映射是矩阵 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 个或更多省份，所以它也应该是一些聪明的算法。

4

3 回答 3

5

使用Voronoi 图

我认为这个不会生成所有可能的地图，但会生成大多数“合理”的地图。

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

算法：

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]}]

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

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

高温高压

于 2010-11-01T15:08:14.960 回答
2

我的时间不多，但一个好主意是：先从左到右然后从右到左添加省份。像

 1111222
 3333322
 3344555        
 0000665

我写了随机数..对吗？

void insert(Matrix matrix){
    lastProvince=0;
    missingProvince=MIN;
    if(matrix.dimensio<MIN*K) throw new RuntimeException("Matrix too small");
    for(y=0;y<matrix.height;y++){
        if(y%2==0){
            for(x=0;x<matrix.width;x++){
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
        }else{
            for(x=matrix.width;x>=0;x--){// is -- not ++
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
         }
   }
}

没有经过测试，但就是这样的想法..

于 2010-11-01T12:53:47.507 回答
2

就在我的脑海中：

  1. 为您需要的每个省份生成一个“种子”。你有一张NxM地图和 L 个省份，只需在 range 中生成 L 个唯一的随机数[0-(N*M-1)]。带有数字的种子的X,Y坐标P是P/M和P%M。

  2. 直到您的所有省份都大于最小尺寸且小于最大尺寸：

    一种。选择一个仍然可以生长的随机省份（大小小于最大值，不完全被其他省份包围）

    湾。将不属于任何省份的随机相邻单元格添加到该省份。

使用这种技术获得飞地的可能性很小，但非常低。您可以增强步骤 b 以检查它们，如果增长会创建一个，则不要增长。

如果在它们自己变得足够大之前被其他省份完全包围，省份也有可能仍然太小。您可以在第 2 步完成后检查并调整。

于 2010-11-01T13:26:42.967 回答