Тестирование смежных ячеек в многоуровневой сетке

Question

Я разрабатываю алгоритм для проверки того, являются ли ячейки на сетке смежными или нет. Уловка заключается в том, что ячейки не находятся на плоской сетке. Они находятся на многоуровневой сетке, например, на рисунке ниже.

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 | 
| - - - - - | - - - - - | 
     .   . 
     .   . 
     .   . 

Эта диаграмма упрощена из-за моей реальной потребности, но концепция такая же. Существует блок верхнего уровня с множеством ячеек внутри него (уровень 1). Каждый блок дополнительно подразделяется на многие другие ячейки (уровень 2). Эти ячейки далее подразделяются на уровни 3, 4 и 5 для моего проекта, но давайте просто придерживаться двух уровней для этого вопроса.

Я получаю входы для моей функции в виде «A8, A9, B7, D3». Это список идентификаторов ячеек, в которых каждый идентификатор ячейки имеет формат (идентификатор уровня 1) (идентификатор уровня 2).

Начнем с сравнения только двух ячеек, A8 и A9. Это легко, потому что они находятся в одном блоке.

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

А9 - сравнение В7 может быть сделано путем проверки, если А является кратным BLOCK_WIDTH и является ли Б (А-BLOCK_WIDTH + 1). Либо это, либо просто проверить наивно, если пара A/B 3-1, 6-4 или 9-7 для лучшей читаемости.

Для B7 - D3 они не смежны, но D3 находится рядом с A9, поэтому я могу выполнить аналогичный тест смежности, как указано выше.

Так что избегайте мелких деталей и фокусируясь на большой картине. Это действительно лучший способ сделать это? Имея в виду следующие моменты:

• Я на самом деле есть 5 уровней не 2, так что я мог бы потенциально получить список как «A8A1A, A8A1B, B1A2A, B1A2B».
• Добавление новой ячейки для сравнения еще требует от меня, чтобы сравнить все другие клетки, прежде чем он (кажется, лучшее, что я мог бы сделать для этого шага является O (п))
• Клетки не все 3x3 блоки, они как раз для моего примера. Они могут быть блоками MxN с разными M и N для разных уровней.
• В моей текущей реализации выше у меня есть отдельные функции для проверки смежности, если ячейки находятся в тех же блоках, если они находятся в отдельных горизонтально смежных блоках или если они находятся в отдельном вертикально смежных блоках. Это означает, что я должен знать позицию двух блоков на текущем уровне, прежде чем я вызову одну из тех функций для слоя ниже.

Судя по сложности необходимости иметь дело с функциями mulitple для разных случаев на разных уровнях и иметь 5 уровней вложенных операторов if. Мне интересно, подходит ли другой дизайн. Возможно, более рекурсивное решение, использование других структур данных или, возможно, отображение всей многоуровневой сетки в одноуровневую сетку (мои быстрые вычисления дают мне около 700 000 + ядерные ячейки). Даже если я иду по этому маршруту, сопоставление от многоуровневого до одного уровня - это нетривиальная задача сама по себе.

Answer 1

• Я на самом деле есть 5 уровней не 2, так что я мог бы потенциально получить список как "A8A1A, A8A1B, B1A2A, B1A2B" ,
• Добавление новой ячейки для сравнения еще требует от меня, чтобы сравнить все другие клетки, прежде чем он (кажется, лучшее, что я мог бы сделать для этого шага является O (п))
• Клетки не все 3x3 блоки, они как раз для моего примера. Они могут быть блоками MxN с разными M и N для разных уровней .

Я не вижу проблемы с этими точками: если клетка не смежная на самом высоком уровне один, то мы можем остановить вычисления прямо там, и мы не должны вычислять смежности по наименьшему уровни. Если есть только пять уровней, вы сделаете не более пяти вычислений смежности, которые должны быть точными.

• В моей текущей реализации выше, у меня есть отдельные функции, чтобы проверить смежности, если клетки находятся в одних и тех же блоках, если они находятся в отдельных соседних по горизонтали блоков, или если они находятся в отдельных вертикально смежных блоках. Это означает, что я должен знать положение двух блоков на текущем уровне, прежде чем я вызову одну из этих функций для слоя ниже.

Вы должны попробовать переписать это. Там должно быть только два метода: один, который вычисляет ли две ячейки являются смежными и один, который вычисляет ли две клетки примыкают на заданном уровне:

• RelativePosition isAdjacent(String cell1, String cell2);
• RelativePosition isAdjacentAtLevel(String cell1, String cell2, int level);

Метод isAdjacent звонки метод isAdjacentAtLevel для каждого уровня. Я не уверен, что cell1 или cell2 всегда содержит информацию обо всех уровнях, но isAdjacent может анализировать данные строки ячеек и соответствующим образом выполнять соответствующие проверки смежности уровня. Когда две ячейки не смежны на определенном уровне, тогда все более глубокие уровни не нужно проверять.

Метод isAdjacentAtLevel должен делать: поиск М и Н для данного уровня, извлекать информацию из cell1 и cell2 данного уровня и выполняет вычисление смежности. Вычисление должно быть одинаковым для каждого уровня, так как каждый уровень сам по себе имеет одну и ту же структуру блока.

Answer 2

Рассчитать и сравнить абсолютные координаты x и y для самого низкого уровня.

Для примера (при условии, что int index0 = 0 для A, 1 для B, ... и index1 = 0 ...8):

int x = (index0 % 3) * 3 + index1 % 3; 
int y = (index0/3) * 3 + index1/3; 

В целом, учитывая

int[] WIDTHS; // cell width at level i 
int[] HEIGHTS; // cell height at level i 

// indices: cell index at each level, normalized to 0..WIDTH[i]*HEIGHT[i]-1 
int getX (int[] indices) { 
    int x = 0; 
    for (int i = 0; i < indices.length; i++) { 
    x = x * WIDTHS[i] + indices[i] % WIDTHS[i]; 
    } 
    return x; 
} 

int getY (int[] indices) { 
    int y = 0; 
    for (int i = 0; i < indices.length; i++) { 
    y = y * HEIGHTS[i] + indices[i]/WIDTHS[i]; 
    } 
    return x; 
} 

Answer 3

Вы можете использовать кривую заполнения пространства, например кривую peano или кривую z morton.