Qiitaに記事を投稿しました。
概要
フラクショナルカスケーディングは2次元領域において, 層状領域木を用いて指定した長方形領域に含まれる点を高速に探索する技術です。問い合わせ時間は,
はデータ点数,
は報告される点の個数です[1]。
フラクショナルカスケーディングについて, 詳しくは[1], もしくは [2, 3]を参考にしてください。 このフラクショナルカスケーディングをPythonで実装しました。
参考
[1] De Berg, Mark, et al. "コンピュータ・ジオメトリ 計算幾何学: アルゴリズムと応用." (2000) 第5章
[2] Shunya Satake. JOIss2013, https://www.slideshare.net/satashun/2013-25814388
[3] okuraofvegetable. 直交領域探索, https://www.slideshare.net/okuraofvegetable/ss-65377588
