CODEWITHSUNDEEP
javaalgorithmgridpartitioning
dlwells02
dlwells02

Reputation: 133

Algorithm to split 2D rectangular grid into smaller grids

I have a 2D grid built using ArrayLists in Java, and would like to split the grid into a given number of smaller grids.

The task I am working on is developing a simulator for the distribution of a game map over multiple servers, which is why I need to split the smaller map into servers.

I have two questions really, the first is given a X by Y rectangle (the map) and a number of parts to split it into N, how can I partition the regular into N smaller (but preferably equal in area) rectangles.

Secondly, I would appreciate suggestions in how to implement the above methodology in terms of 2D arraylists.

Upvotes: 1

Views: 6679

Answers (2)

Russell Zahniser
Russell Zahniser

Reputation: 16364

If n happens to be square, you could split the grid by cutting into sqrt(n) slices on each direction. Otherwise, horizontal stripes would work (if it's not a problem that the pieces are not similar in shape to the whole map). If keeping the shapes reasonable is more important than keeping them of equal size, consider an algorithm where you start from the whole grid and keep splitting the largest piece in half until you have the required number of pieces.

When it comes to cutting out a slice of the grid, I'm assuming by a 2D ArrayList you mean a List<List<?>>, where list.get(x).get(y) is the item at (x, y). Then you can just use subList() in both directions:

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

Note that the grid slice created here references back into the original grid and changes to the slice will be reflected in the full grid. You could make copies of everything instead if you wanted to avoid this.

Upvotes: 1

hypercode
hypercode

Reputation: 488

Answering the first question on splitting an X-by-Y rectangle into N smaller rectangles of equal area...

I think the best approach is to break up the rectangle in N sub-rects that each maintain the same aspect ratio of the main rect.

N should be such that sqrt(N) yields an integral answer (e.g. N=36, sqrt(N)=6). Therefore, X-by-Y is broken down into sqrt(N)-by-sqrt(N) sub-rects. The sub-rect size (Xs,Ys) is calculated like so:

Xs = X / sqrt(N)

Ys = Y / sqrt(N)

This approach will always give you N equal sub-rects as long as sqrt(N) is an integral value. Depending upon the value of N, you may have to compensate for integer truncation errors by making some of the sub-rects slightly larger to fully cover the entire main rectangle.

There is another approach that is calculated by dividing the area of the main rectangle by N, then taking the square root of that result to come up with a sub-square that's M-by-M, but that's coarser than the above approach.

Upvotes: 4

Related Questions