交差する長方形の探索

◯ 概要

◯ 用語

stub query ... 線分と交差する別の線分を探すこと, 長方形と交差する別の長方形を探すこと

◯ 課題

 どうやって2次元に拡張するの?

アルゴリズムは基本1次元のアルゴリズムで説明されていて、2次元について簡単に概要で説明されている程度である(segment tree, interval tree)。つまり線分同士の stub query について言及されている。

1. kd 木, 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木の特殊なものらしい。

とどの詰まるところ、区間木は領域を2分割することを繰り返して木を作成する。挿入時は、該当する領域を持つ葉に長方形を挿入する。分割された領域にいれられない、領域の境界線をまたぐ長方形も存在するので、その場合は中間ノードにあるリストにいれる。

あまり木を使ったことがなかったので、「リストにいれる」と言う文言、もっと言えば「リスト」という単語を見た瞬間に O(n) に、だいぶ近づいてしまうんじゃないの?って疑問に思ったけど、結局挿入される長方形の性質次第かな..

わかりやすい。理解はしてない。注意したいのは 検索クエリ > 区間 の項目で説明されているのは、区間木ではなく別の木を使うことを示している。検索クエリ > 点の項目で区間木を使うように言っている。つまり2つの木を使う形での実装を説明している。

簡単にやりたければ1つだけでも良さそう。

検索クエリ > 区間 の項目で説明されている操作は包含されない、交差する木の検索を行なっている。そのような検索はでは領域木 range tree を使うのが良いのかもしれない。

領域木は質問長方形の中に含まれる点を返すアルゴリズムのようである。なので、長方形の四隅の1点を含むかどうかの判定に使えば良さそう。

3. 区分木, segment tree

区分木も、リストにいれると言う文言を見た瞬間に O(n) になるんじゃないの?って疑問に思ったけど、そうでもなさそう。木なのにリスト使うの?みたいな違和感が最初はすごくあった。

各中間ノードに、交差する長方形をリストに格納する(この理解であっているのだろうか)。複数の中間リストに同じ長方形を登録することになる。だから stub query だけならいいけど delete を実装するときは面倒そう。

削除対象の長方形を探索して、該当する各中間ノードから削除するみたいな.. あるいは長方形に所属する中間ノードへのポインタリストを渡しておくのか.. うーん。

資料の中でリストのことを standard list って表現されてて、逆に特殊な用語なのかなと思ってヘッ?ってなった。

◯ 動的に追加, 削除は基本的にはできない様子

動的に追加、削除は厳しそうで、採用を断念しようかと考えている..., 行けるかなと思ったのに。

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

5. R木, R-tree

思いついて、自力で実装しようとしていた... Web を巡回してたら見つかった。

基本的な考え方は、なるべく最小の面積になるように長方形をグルーピングしていくこと。

上の木とは違い、最初から動的な平衡木であること。つまり、長方形の追加削除に合わせて、高さが低くなるように木が再構築されることを前提に設計されています。

ただし、木のノード削除の際に発生する木の再構築にかかる処理が、なんだか重そう。 頻繁に追加削除が発生するならしない方が良いか..

動的長方形交差, Dynamic rectangular intersection

長方形の挿抜に合わせて動的に木を再構築するように実装しようとすると、一気に問題の難易度が上がる...。

◯ 課題

 どうやって insert, delete を実装するの?

stub query はあるけど、 insert, delete の実装、アルゴリズムが見当たらないことが多い。

あっても木の再構築にかかる記述がなく、これでいいの?って気分になる。

上記のデータ構造は、R木以外は平衡木ではない。

◯ 分かりやすい、理解はできたとは言っていない

◯ 難しくてわからない。わかったら、すごく勉強になりそう...

探索

この辺りの復習も... - 深さ優先探索と幅優先探索 | 高校数学の美しい物語 - よく分からない深さ優先探索 | Qiita - 平面走査法, Sweep line algorithm