.net - 重なり合わない長方形でのヒットテストのアルゴリズム

Question

囲んでいる長方形をカバーする重複しない長方形のコレクションがあります。マウスクリックで含まれている長方形を見つける最良の方法は何ですか？

明白な答えは、長方形の配列を持ち、それらを順番に検索して、検索をO（n）にすることです。アルゴリズムがO（n）よりも小さくなるように位置別に並べ替える方法はありますか？たとえば、O（log n）またはO（sqrt（n））ですか？

score 6 · Accepted Answer

四角形または kd ツリーで四角形を整理できます。これにより、O(log n) が得られます。それが主流の方法です。

この問題のもう 1 つの興味深いデータ構造は、R ツリーです。多数の長方形を処理する必要がある場合、これらは非常に効率的です。

次に、画面と同じサイズのビットマップを単純に生成し、「長方形なし」のプレースホルダーで塗りつぶし、ヒット長方形インデックスをそのビットマップに描画する O(1) メソッドがあります。ルックアップは次のように単純になります。

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

明らかに、その方法は、長方形がそれほど頻繁に変更されず、ビットマップ用のメモリを節約できる場合にのみうまく機能します。

score 1 · Accepted Answer

区間木を作成します。区間木を照会します。MITプレスの「アルゴリズム」を参照してください。

区間木は、赤黒木として実装するのが最適です。

通常、長方形をクリックして位置を変更する場合にのみ、長方形を並べ替えることをお勧めします。

異なる軸のインデックスを個別にビルドビルドしていることを覚えておく必要があります。たとえば、XとYの間隔がオーバーラップしているかどうかを確認する必要があります。明らかな最適化の1つは、いずれかのX間隔のオーバーラップのみをチェックし、すぐにYのオーバーラップをチェックすることです。

また、ほとんどのストックまたは「クラスブック」区間木は、単一の区間のみをチェックし、単一の区間のみを返します（ただし、「重複しない」と言ったのではありませんか？）

score 0 · Accepted Answer

0

それらを四分木に押し込みます。

于 2008-09-18T22:48:40.150 に答える

score 0 · Accepted Answer

0

BSPツリーを使用して長方形を保存します。

于 2008-09-18T22:50:09.570 に答える

4 に答える 4