算法二維矩形網格分割成更小網格

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的子平方，但這比粗糙的以上方法。