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

概要

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

フラクショナルカスケーディングについて, 詳しくは[1], もしくは fractional cascadingを参考にしてください。

ネットでもあまり, 実装例を見かけないので
このフラクショナルカスケーディングをPythonで実装しました。

コード

開発環境: macOS Mojave(10.14.2), Python(>=3.7)
実装参考: [1]
https://gist.github.com/cf012cbc3caca173d2b9d2a89977f3bf

使い方

from fractional_cascading import Tree, Point, Rectangle

層状領域木の作成

# データ準備
points = list()
points.append(Point(name='A', loc=(1, 5))) # loc(x座標, y座標)
points.append(Point(name='B', loc=(2, 2)))
points.append(Point(name='C', loc=(4, 8)))
points.append(Point(name='D', loc=(5, 7)))
points.append(Point(name='E', loc=(5, 5)))
points.append(Point(name='F', loc=(8, 6)))
points.append(Point(name='E', loc=(7, 1)))

# 木のインスタンスの作成
tree = Tree(sample_data)

# treeをpickleで保存
# tree.dump_pickle(pickle_file='sample.pickle')
# treeをpickleから読み込み
# tree = Tree(pickle_file='sample.pickle')

長方形領域探索

# 探索領域を指定
R = Rectangle(x_min=1.5, x_max=5.5,
              y_min=1.5, y_max=5.5)

# フラクショナルカスケーディングを実行 / 結果の出力
for elm in tree.query(R):
    print(elm)
>> name: B, loc: (2, 2)
>> name: E, loc: (5, 5)

参考

[1] De Berg, Mark, et al. "コンピュータ・ジオメトリ 計算幾何学: アルゴリズムと応用." (2000) 第5章
[2] https://www.slideshare.net/secret/48dF2L2saJOz2e
コード: https://gist.github.com/cf012cbc3caca173d2b9d2a89977f3bf