将二维矩形网格分割为较小网格的算法
我有一个在Java中使用ArrayLists构建的2D网格，并希望将网格拆分为给定数量的较小网格。
我正在做的任务是开发一个模拟器，用于在多个服务器上分发游戏地图，这就是为什么我需要将较小的地图拆分为多个服务器的原因。
我真的有两个问题，第一个是给出一个X x Y的矩形(地图)和一些部分来将它分割成N个，我如何将规则分割成N个更小的(但最好是面积相等的)矩形。
其次，我希望就如何在二维数组列表中实现上述方法提出建议。
回答 2
Stack Overflow用户
发布于 2012-01-07 02:26:53
回答第一个问题，将一个X×Y的矩形分成N个面积相等的小矩形……
我认为最好的方法是将矩形分成N个子矩形，每个子矩形保持主矩形的纵横比相同。
N应该是这样的：sqrt(N)产生一个完整的答案(例如N=36，sqrt(N)=6)。因此，X-by-Y被分解为sqrt(N)-by-sqrt(N)子矩形。子矩形尺寸(Xs，Ys)的计算方法如下：
Xs =X/ sqrt(N)
Ys =Y/ sqrt(N)
只要sqrt(N)是一个整数值，这种方法将始终为您提供N个相等的子矩形。根据N的值，您可能必须通过使一些子矩形稍微大一点以完全覆盖整个主矩形来补偿整数截断错误。
还有另一种方法，计算方法是将主矩形的面积除以N，然后取结果的平方根，得出一个M乘以M的子正方形，但这比上面的方法更粗糙。
Stack Overflow用户
发布于 2012-01-07 02:26:01
如果n恰好是正方形，您可以通过在每个方向上切割成sqrt(n)切片来拆分网格。否则，水平条纹将会起作用(如果这不是一个问题，即碎片的形状与整个地图不相似的话)。如果保持形状合理比保持大小相等更重要，请考虑一种算法，该算法从整个网格开始，将最大的部分一分为二，直到获得所需数量的部分。
当涉及到剪切网格的一部分时，我假设2D ArrayList指的是List<List<?>>，其中list.get(x).get(y)是(x，y)处的项。然后，您可以只在两个方向上使用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;
}请注意，此处创建的网格切片引用回原始网格，对切片所做的更改将反映在整个网格中。如果你想避免这种情况，你可以复制所有的东西。
https://stackoverflow.com/questions/8761798
复制相似问题
腾讯云开发者
