交差する長方形の探索

動的長方形交差 Dynamic rectangular intersection

結局自分がやろうとしていることは全てのパターンを探さないといけないので…
線形探索 O(n) から O(log n) くらいには変わるみたい。

BVH

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

kd 木, kd tree

quad tree でもできるよ的な記述を見かける…

四分木, quad 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.

区分木, segment tree

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

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

○ 導入に適した記事

○ 難しい記事

○ 日本語の記事(今回はあまり参考にできなかったもの)

区間木 interval tree

interval tree の implementation は見つかった.., segment tree は見つからない..

探索

この辺りの復習も…