重なり合わない四角形でのヒット テストのアルゴリズム

Question

囲む長方形を覆う、重なり合わない長方形のコレクションがあります。マウスクリックを含む四角形を見つける最良の方法は何ですか?

明らかな答えは、長方形の配列を用意し、それらを順番に検索して、検索を O(n) にすることです。アルゴリズムが O(n) 未満、たとえば O(log n) または O(sqrt(n)) になるように、位置によってそれらを並べる方法はありますか?

Answer 1

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

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

http://en.wikipedia.org/wiki/R-tree

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

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

明らかに、この方法がうまく機能するのは、四角形がそれほど頻繁に変更されず、ビットマップ用のメモリを確保できる場合に限られます。

Answer 2

インターバルツリーを作成します。間隔ツリーをクエリします。MIT プレスの「アルゴリズム」を参照してください。

間隔ツリーは、赤黒ツリーとして実装するのが最適です。

通常、四角形の位置を変更するよりも四角形をクリックする回数が増える場合にのみ、四角形を並べ替えることをお勧めします。

異なる軸のインデックスを個別に構築する必要があることに留意する必要があります。たとえば、X と Y の間隔が重なっているかどうかを確認する必要があります。明らかな最適化の 1 つは、どちらかの X 間隔での重複のみをチェックし、その後すぐに Y での重複をチェックすることです。

また、ほとんどのストックまたは「クラスブック」間隔ツリーは、単一の間隔のみをチェックし、単一の間隔のみを返します (ただし、「重複しない」と言いましたよね?)。

Answer 3

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

Answer 4

使う BSP 長方形を格納するツリー。