8 commits | Last commit ≈ 2 months ago
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
The kd-tree is a space-partitioning data structure for organizing points in a k-dimensional space.
build_kdtree.py
Builds a kd-tree from a set of points.
nearest_neighbour_search.py
Performs nearest neighbour search using the built kd-tree.
hypercube_points.py
Generates n-Dimensional Points Uniformly in an n-Dimensional Hypercube.
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}")