Testing for Adjacent Cells In a Multi-level Grid
- by Steve
I'm designing an algorithm to test whether cells on a grid are adjacent or not.
The catch is that the cells are not on a flat grid. They are on a multi-level grid such as the one drawn below.
Level 1 (Top Level)
| - - - - - |
| A | B | C |
| - - - - - |
| D | E | F |
| - - - - - |
| G | H | I |
| - - - - - |
Level 2
| -Block A- | -Block B- |
| 1 | 2 | 3 | 1 | 2 | 3 |
| - - - - - | - - - - - |
| 4 | 5 | 6 | 4 | 5 | 6 | ...
| - - - - - | - - - - - |
| 7 | 8 | 9 | 7 | 8 | 9 |
| - - - - - | - - - - - |
| -Block D- | -Block E- |
| 1 | 2 | 3 | 1 | 2 | 3 |
| - - - - - | - - - - - |
| 4 | 5 | 6 | 4 | 5 | 6 | ...
| - - - - - | - - - - - |
| 7 | 8 | 9 | 7 | 8 | 9 |
| - - - - - | - - - - - |
. .
. .
. .
This diagram is simplified from my actual need but the concept is the same. There is a top level block with many cells within it (level 1). Each block is further subdivided into many more cells (level 2). Those cells are further subdivided into level 3, 4 and 5 for my project but let's just stick to two levels for this question.
I'm receiving inputs for my function in the form of "A8, A9, B7, D3". That's a list of cell Ids where each cell Id has the format (level 1 id)(level 2 id).
Let's start by comparing just 2 cells, A8 and A9. That's easy because they are in the same block.
private static RelativePosition getRelativePositionInTheSameBlock(String v1, String v2) {
RelativePosition relativePosition;
if( v1-v2 == -1 ) {
relativePosition = RelativePosition.LEFT_OF;
}
else if (v1-v2 == 1) {
relativePosition = RelativePosition.RIGHT_OF;
}
else if (v1-v2 == -BLOCK_WIDTH) {
relativePosition = RelativePosition.TOP_OF;
}
else if (v1-v2 == BLOCK_WIDTH) {
relativePosition = RelativePosition.BOTTOM_OF;
}
else {
relativePosition = RelativePosition.NOT_ADJACENT;
}
return relativePosition;
}
An A9 - B7 comparison could be done by checking if A is a multiple of BLOCK_WIDTH and whether B is (A-BLOCK_WIDTH+1).
Either that or just check naively if the A/B pair is 3-1, 6-4 or 9-7 for better readability.
For B7 - D3, they are not adjacent but D3 is adjacent to A9 so I can do a similar adjacency test as above.
So getting away from the little details and focusing on the big picture. Is this really the best way to do it? Keeping in mind the following points:
I actually have 5 levels not 2, so I could potentially get a list like "A8A1A, A8A1B, B1A2A, B1A2B".
Adding a new cell to compare still requires me to compare all the other cells before it (seems like the best I could do for this step
is O(n))
The cells aren't all 3x3 blocks, they're just that way for my example. They could be MxN blocks with different M and N for
different levels.
In my current implementation above, I have separate functions to check adjacency if the cells are in the same blocks, if they are in
separate horizontally adjacent blocks or if they are in separate
vertically adjacent blocks. That means I have to know the position of
the two blocks at the current level before I call one of those
functions for the layer below.
Judging by the complexity of having to deal with mulitple functions for different edge cases at different levels and having 5 levels of nested if statements. I'm wondering if another design is more suitable. Perhaps a more recursive solution, use of other data structures, or perhaps map the entire multi-level grid to a single-level grid (my quick calculations gives me about 700,000+ atomic cell ids). Even if I go that route, mapping from multi-level to single level is a non-trivial task in itself.
