KD-Tree-Python

KD-Tree Implementation in Python

1
contributor
8 commits | Last commit 2 months ago

Cite this software

What KD-Tree-Python can do for you

Python NumPy GitHub

DOI

KD-Tree Implementation in Python

This repository contains Python implementation of the kd-tree data structure and performing k-nearest neighbour search.

Its Matlab implementation is located here: KD-Tree-Matlab

About

The kd-tree is a space-partitioning data structure for organizing points in a k-dimensional space.

Mathematica Link

Scripts

  1. build_kdtree.py

    Builds a kd-tree from a set of points.

  2. nearest_neighbour_search.py

    Performs nearest neighbour search using the built kd-tree.

  3. hypercube_points.py

    Generates n-Dimensional Points Uniformly in an n-Dimensional Hypercube.

Example Usage

from kdtree.build_kdtree import build_kdtree
from kdtree.nearest_neighbor_search import nearest_neighbor_search
from examples.hypercube_points import hypercube_points

num_points = 5000
cube_size = 10
num_dimensions = 10

points = hypercube_points(num_points, cube_size, num_dimensions)
hypercube_kdtree = build_kdtree(points.tolist())

query_point = np.random.rand(num_dimensions).tolist()

nearest_point, nearest_dist, nodes_visited = nearest_neighbor_search(hypercube_kdtree, query_point)

print(f"Query point: {query_point}")
print(f"Nearest point: {nearest_point}")
print(f"Distance: {nearest_dist:.4f}")
print(f"Nodes visited: {nodes_visited}")
Keywords
Programming language
  • Python 100%
License
</>Source code

Contributors