空間データ構造

本稿は SciPy のモジュール scipy.spatial について述べる。このモジュールには次の問題を解くための機能がある。

  • Delaunay 三角形分割

  • Voronoi 図

  • 点群の凸包

  • k-D 木

KDTree

空間上のある点とある点群に対して、最も近い距離にあるものを探索するにはクラス scipy.spatial.KDTree を利用するのがよい。

Reference Guide の例を一部改変したものを記す。以下の説明では、ある点とある点群をそれぞれ target, points としてある。コード的な手順は次のとおりとなる。

  1. points を array_like の形式で用意する。点は普通は三次元空間の座標となる。

  2. points からクラス KDTree のインスタンスをコンストラクター呼び出しで生成する。

  3. 評価したい target を決める。

  4. メンバーメソッド query を呼び出し、距離と点群のインデックスを得る。

コード例を示す。

#!/usr/bin/env python
"""kdtree.py: Demonstrate class KDTree of SciPy.
"""
import numpy as np
from scipy.spatial import KDTree

# pylint: disable=invalid-name

# Genrate 3D points: (0, 0, 0), (0, 0, 10), (0, 0, 20), ...
x, y, z = np.mgrid[0:100:10, 0:100:10, 0:100:10]
points = list(zip(x.ravel(), y.ravel(), z.ravel()))

# Construct a KDTree.
tree = KDTree(points)

# A target point included in [0, 100) * [0, 100) * [0, 100).
target = [43.831, 54.762, 83.131]
print(f"Target: {target}")

# Query for the closest point.
dist, index = tree.query(target, eps=0.01)
print(f"Closest: {tree.data[index]}")
print(f"Distance: {dist}")

私の環境での実行結果を記す。

Target: [43.831, 54.762, 83.131]
Closest:  [40 50 80]
Distance: 6.867049293546685