サブロウ丸

主にプログラミングと数学

【Python】フラクショナルカスケーディング実装

Qiitaに記事を投稿しました。

概要

ラクショナルカスケーディングは2次元領域において, 層状領域木を用いて指定した長方形領域に含まれる点を高速に探索する技術です。問い合わせ時間は O(\log n+k),  nはデータ点数,  kは報告される点の個数です[1]。

f:id:inarizuuuushi:20190208103143p:plain

ラクショナルカスケーディングについて, 詳しくは[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