algorithm - マルチレベルグリッド内の隣接セルのテスト

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 にさらに細分化されていますが、この質問では 2 つのレベルに固執しましょう。

関数の入力を「A8、A9、B7、D3」の形式で受け取ります。これはセル ID のリストで、各セル ID の形式は (レベル 1 ID)(レベル 2 ID) です。

A8 と A9 の 2 つのセルだけを比較することから始めましょう。同じブロックにあるので簡単です。

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

A9 - B7 の比較は、A が BLOCK_WIDTH の倍数であるかどうか、および B が (A-BLOCK_WIDTH+1) であるかどうかをチェックすることによって実行できます。それか、読みやすくするために、A/B ペアが 3-1、6-4、または 9-7 であるかどうかを単純に確認します。

B7 ～ D3 については、それらは隣接していませんが、D3 は A9 に隣接しているため、上記と同様の隣接テストを実行できます。

そのため、細かいことは気にせず、全体像に焦点を当てます。これは本当に最善の方法ですか？次の点に注意してください。

実際には 2 ではなく 5 つのレベルがあるため、「A8A1A、A8A1B、B1A2A、B1A2B」のようなリストを取得できる可能性があります。
比較する新しいセルを追加するには、その前の他のすべてのセルを比較する必要があります (このステップで実行できる最善の方法は O(n) のようです)。
セルはすべて 3x3 ブロックではなく、私の例ではそのようになっています。それらは、レベルごとに異なる M と N を持つ MxN ブロックである可能性があります。
上記の現在の実装では、セルが同じブロックにあるか、水平方向に隣接する別々のブロックにあるか、または垂直方向に隣接する別々のブロックにあるかをチェックする個別の関数があります。つまり、下のレイヤーに対してこれらの関数のいずれかを呼び出す前に、現在のレベルでの 2 つのブロックの位置を知る必要があります。

さまざまなレベルでさまざまなエッジケースの複数の関数を処理する必要があり、ネストされた if ステートメントが 5 レベルあるという複雑さから判断します。別のデザインが適しているかどうかを考えています。おそらく、より再帰的なソリューション、他のデータ構造の使用、またはマルチレベルグリッド全体をシングルレベルグリッドにマップする (私の簡単な計算で、約 700,000 以上のアトミックセル ID が得られます)。その道を進んだとしても、マルチレベルからシングルレベルへのマッピングはそれ自体が重要な作業です。

score 0 · Accepted Answer

最低レベルの絶対 x 座標と y 座標を計算して比較します。

int index0例 ( A の場合は = 0、B の場合は 1、... および= 0...8 と仮定index1):

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

score 0 · Accepted Answer

実際には 2 ではなく 5 つのレベルがあるため、「A8A1A、A8A1B、B1A2A、B1A2B」のようなリストを取得できる可能性があります。

比較する新しいセルを追加するには、その前の他のすべてのセルを比較する必要があります (このステップで実行できる最善の方法は O(n) のようです)。

セルはすべて 3x3 ブロックではなく、私の例ではそのようになっています。それらは、レベルごとに異なる M と N を持つ MxN ブロックである可能性があります。

これらのポイントに問題はありません。セルが最高レベルで隣接していない場合は、そこで計算を停止でき、下位レベルで隣接関係を計算する必要はありません。レベルが 5 つしかない場合は、最大で 5 つの隣接計算を行うだけで問題ありません。

上記の現在の実装では、セルが同じブロックにあるか、水平方向に隣接する別々のブロックにあるか、または垂直方向に隣接する別々のブロックにあるかをチェックする個別の関数があります。つまり、下のレイヤーに対してこれらの関数のいずれかを呼び出す前に、現在のレベルでの 2 つのブロックの位置を知る必要があります。

これを書き直してみてください。メソッドは 2 つだけにする必要があります。1 つは 2 つのセルが隣接しているかどうかを計算する方法で、もう 1 つは 2 つのセルが特定のレベルで隣接しているかどうかを計算する方法です。

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

メソッドは、レベルごとにisAdjacentメソッドを呼び出します。すべてのレベルの情報が常に含まれてisAdjacentAtLevelいるかどうかはわかりませんcell1が、指定されたセル文字列を分析し、それに応じて適切なレベルの隣接チェックを呼び出すことができます。2 つのセルが特定のレベルで隣接していない場合、すべてのより深いレベルをチェックする必要はありません。cell2isAdjacent

メソッドは、指定されたレベルのMとNisAdjacentAtLevelを検索し、指定されたレベルから情報を抽出し、隣接計算を実行する必要があります。各レベルはそれ自体が同じブロック構造を持っているため、計算は各レベルで同じでなければなりません。cell1cell2

score 0 · Accepted Answer

0

ペアノ曲線や z モートン曲線などの空間充填曲線を使用できます。

于 2012-06-22T22:30:51.577 に答える

algorithm - マルチレベル グリッド内の隣接セルのテスト

3 に答える 3

Related

Reference

algorithm - マルチレベルグリッド内の隣接セルのテスト