算法二维矩形网格分割成更小网格

Question

我在Java中使用的ArrayList二维网格建，想给电网分割成更小网格的给定数。

我工作的任务是制定游戏地图在多个服务器上，这就是为什么我需要较小的地图分成服务器分布的模拟器。

我真的有两个问题，第一个问题是给出一个X乘以Y的矩形（地图）和一些部分将其拆分为N，我怎样才能将规则划分成N个较小（但最好在面积上相等）矩形。

其次，我希望在如何实现2D的ArrayList而言上述方法的建议。

Answer 1

如果n恰好是正方形，可以切成SQRT（n）的切片的每个方向上分割网格。否则，水平条纹将起作用（如果它不是一个问题，那些件在形状上与整个地图不相似）。如果保持形状合理比保持大小相同更重要，可以考虑一种算法，从整个网格开始，并将最大的一块分成两半，直到获得所需数量的块。

当谈到切割网格切片时，我假设你的意思是一个List<List<?>>，其中list.get(x).get(y)是（x，y）处的项目的2D ArrayList。然后，你可以只使用subList()在两个方向：

List<List<?>> split(List<List<?>> in, int x1, int y1, int x2, int y2) { 
    List<List<?>> out = new ArrayList<List<?>>(w); 
    for(List<?> column : in.sublist(x1, x2)) { 
     out.add(column.subList(y1, y2)); 
    } 
    return out; 
} 

List<List<List<?>>> partitionEqualAspect(List<List<?>> grid, int n) { 
    int w = grid.size(); 
    int h = grid.get(0).size(); 
    int cols = (int)(sqrt(n) + .5); 

    // This many columns have (cols - 1) rows 
    int shortCols = Math.max(0, cols * cols - n); 
    // This many columns have (cols + 1) rows 
    int longCols = Math.max(0, n - cols * cols); 

    List<List<List<?>>> tiles = new ArrayList<List<List<?>>>(); 
    for(int c = 0; c < cols; ++c) { 
     int rows = cols + (c < shortCols ? -1 : c >= cols - longCols ? 1 : 0); 
     for(int r = 0; r < rows; ++r) { 
     tiles.add(split(grid, 
         w * c/cols, h * r/rows, 
         w * (c + 1)/cols, h * (r + 1)/rows)); 
     } 
    } 
    return tiles; 
} 

注意的是，这里创建的网格片引用回到原来的电网和切片的变化将在满格中反映出来。如果你想避免这种情况，你可以复制一切。

Answer 2

回答第一个问题上分裂的X通过-Y矩形分成相等的面积N个较小的矩形...

我认为最好的办法是将其分割成N个子rects每个维持矩形主矩形的纵横比相同。

N必须使得SQRT（N）产生一个积分的答案（例如N = 36，SQRT（N）= 6）。因此，X-通过-Y被分解成SQRT（N） -by- SQRT（N）子rects。子矩形大小（XS，YS）的计算如下所示：

两个X = X/SQRT（N）

伊苏= Y/SQRT（N）

这种方法将总是给你Ñ只要sqrt（N）是一个整数值。根据N的值，你可能需要补偿整数截断误差，方法是使一些子矩阵稍大一些，以完全覆盖整个主矩形。

还有另一种方法是通过将主矩形的面积除以N来计算，然后将该结果的平方根提出M乘M的子平方，但这比粗糙的以上方法。