１対多の当たり判定、長方形の交差問題
◯ 概要
- Rectangle Intersection - Princeton University | Coursera
長方形交差問題のアルゴリズムの概要や応用分野を紹介
◯ 用語
stub query ... 線分と交差する別の線分を探すこと, 長方形と交差する別の長方形を探すこと
◯ サンプルコード
サンプルコードを書きました。 https://github.com/domodomodomo/rectangle_intersection
◯ 課題
どうやって２次元に拡張するの？
アルゴリズムは基本１次元のアルゴリズムで説明されていて、２次元について簡単に概要で説明されている程度である（segment tree, interval tree）。つまり線分同士の stub query について言及されている。
1. kd 木, kd tree
- 2D Range Query - KD-tree and Range tree
- find overlapping rectangles algorithm
- Querying a collection of rectangles for the overlap of an input rectangle
- kd tree
◯ 動的に追加, 削除は基本的にはできない様子
回答が秀逸すぎて泣ける...
KD-trees are definitively not dynamic enough to be considered, honestly. Moving a few units can easily require you to rebuild the whole KD-Tree. Plus, a KD-tree is very efficient for queries, but not so much for neighbor searching.
Fully dynamic KD-Tree vs. Quadtree?
2. 区間木, interval tree
Wikipedia によると kd木の特殊なものらしい。
とどの詰まるところ、区間木は領域を２分割することを繰り返して木を作成する。挿入時は、該当する領域を持つ葉に長方形を挿入する。分割された領域にいれられない、領域の境界線をまたぐ長方形も存在するので、その場合は中間ノードにあるリストにいれる。
あまり木を使ったことがなかったので、「リストにいれる」と言う文言、もっと言えば「リスト」という単語を見た瞬間に O(n) に、だいぶ近づいてしまうんじゃないの？って疑問に思ったけど、結局挿入される長方形の性質次第かな..
- interval Trees, Priority Search Trees, Segment Trees
interval tree の 4 枚目のスライドが分かりやすい。 - How do segment trees solve the Stabbing Problem?
interval tree の implementation は見つかった.., segment tree は見つからない..
わかりやすい。理解はしてない。注意したいのは 検索クエリ > 区間 の項目で説明されているのは、区間木ではなく別の木を使うことを示している。検索クエリ > 点の項目で区間木を使うように言っている。つまり２つの木を使う形での実装を説明している。
簡単にやりたければ１つだけでも良さそう。
検索クエリ > 区間 の項目で説明されている操作は包含されない、交差する木の検索を行なっている。そのような検索はでは領域木 range tree を使うのが良いのかもしれない。
領域木は質問長方形の中に含まれる点を返すアルゴリズムのようである。なので、長方形の四隅の１点を含むかどうかの判定に使えば良さそう。
3. 区分木, segment tree
区分木も、リストにいれると言う文言を見た瞬間に O(n) になるんじゃないの？って疑問に思ったけど、そうでもなさそう。木なのにリスト使うの？みたいな違和感が最初はすごくあった。
各中間ノードに、交差する長方形をリストに格納する（この理解であっているのだろうか）。複数の中間リストに同じ長方形を登録することになる。だから stub query だけならいいけど delete を実装するときは面倒そう。
削除対象の長方形を探索して、該当する各中間ノードから削除するみたいな.. あるいは長方形に所属する中間ノードへのポインタリストを渡しておくのか.. うーん。
資料の中でリストのことを standard list って表現されてて、逆に特殊な用語なのかなと思ってヘッ？ってなった。
- segment tree and interval tree - lecture 5
この segment tree の説明は分かりやすい。 - tutorial stubbing
- Dynamic Segment Trees | CORDEFORCES]
動的なものを作ろうとしているが、 よくわからない。 - プログラミングコンテストでのデータ構造 Union-Find 木, セグメント木
領域探索とは違うけど分かりやすくて勉強になります。
◯ 動的に追加, 削除は基本的にはできない様子
動的に追加、削除は厳しそうで、採用を断念しようかと考えている..., 行けるかなと思ったのに。
In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, it's a structure that cannot be modified once it's built. A similar data structure is the interval tree.
segment tree | Wikipedia
4. 四分木, quad tree
- JavaScriptで大量のオブジェクトの当たり判定を効率的にとる
これが一番わかりやすい。GitHub のサンプルコードもこれを見て実装した。 - 八分木（モートンオーダー）を使ってエリアを分割して処理負荷を軽減する
- 2D Segment/Quad Tree Explanation with C++ closed
図入りで説明してくれてます。"The idea of 2D segment tree is nothing but the Quad Tree" ２次元セグメント木の考え方は、四分木以外の何者でもないんだ。そうです。 - Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space
四分木の実装の仕方
5. R木, R-tree
思いついて、自力で実装しようとしていた... Web を巡回してたら見つかった。
基本的な考え方は、なるべく最小の面積になるように長方形をグルーピングしていくこと。
上の木とは違い、最初から動的な平衡木であること。つまり、長方形の追加削除に合わせて、高さが低くなるように木が再構築されることを前提に設計されています。
ただし、木のノード削除の際に発生する木の再構築にかかる処理が、なんだか重そう。 頻繁に追加削除が発生するならしない方が良いか..
- 空間インデックス(R-tree)入門
この説明は分かりやすい。 - Bounding Volume Hierarchy (BVH) の実装 - 構築編 | Qiita
R木と似てるけど、ちょっと分野が違うのかな..
動的長方形交差, Dynamic rectangular intersection
長方形の挿抜に合わせて動的に木を再構築するように実装しようとすると、一気に問題の難易度が上がる...。
◯ 課題
どうやって insert, delete を実装するの？
stub query はあるけど、 insert, delete の実装、アルゴリズムが見当たらないことが多い。
あっても木の再構築にかかる記述がなく、これでいいの？って気分になる。
上記のデータ構造は、R木以外は平衡木ではない。
◯ 分かりやすい、理解はできたとは言っていない
◯ 難しくてわからない。わかったら、すごく勉強になりそう...
- Dynamic rectangular intersection with priorities
- The Unified Segment Tree and its Application to ...
- 動的長方形探索木 - 長方形の動的交差問題
探索
この辺りの復習も...
