scipy.spatial
Contents
scipy.spatial¶
scipy.spatial can compute triangulations, Voronoi diagrams, and convex hulls of a set of points, by leveraging the Qhull library.
Moreover, it contains KDTree implementations for nearest-neighbor point queries, and utilities for distance computations in various metrics.
Triangulations (qhull)¶
%matplotlib inline
import numpy as np
from scipy.spatial import Delaunay, ConvexHull, Voronoi
import matplotlib.pyplot as plt
points = np.random.rand(30, 2) # 30 random points in 2-D
tri = Delaunay(points)
hull = ConvexHull(points)
voronoi = Voronoi(points)
print ("Neighbour triangles\n",tri.neighbors[0:5])
print ("Simplices\n", tri.simplices[0:5])
print ("Points\n", points[tri.simplices[0:5]])
from scipy.spatial import delaunay_plot_2d
delaunay_plot_2d(tri)
pass
from scipy.spatial import convex_hull_plot_2d
convex_hull_plot_2d(hull)
pass
from scipy.spatial import voronoi_plot_2d
voronoi_plot_2d(voronoi)
pass
KDtree¶
Allows very fast point to point searches.
from scipy.spatial import KDTree, cKDTree
tree = cKDTree(points)
print (tree.data)
%%timeit
tree.query((0.5,0.5))
test_points = np.random.rand(1000, 2) # 1000 random points in 2-D
%%timeit
tree.query(test_points)
more_points = np.random.rand(10000, 2) # 1000 random points in 2-D
big_tree = KDTree(more_points)
%%timeit
KDTree(more_points)
%%timeit
big_tree.query(test_points)
Compare this to the brute-force version¶
At what point does it make sense to use kdTree and not brute-force distance tests ?
The brute force method takes a fixed time per sample point and a fixed cost associated with the N-neighbour distance computation (but this can be vectorised efficiently).
# Brute force version
def brute_force_distance(pts, spt):
d = pts - spt
d2 = d**2
distances2 = np.einsum('ij->i',d2)
nearest = np.argsort(distances2)[0]
return np.sqrt(distances2[nearest]), nearest
# print np.einsum('ij->i',distances2)
print (brute_force_distance(more_points, (0.0,0.0)))
print (big_tree.query((0.0,0.0)))
%%timeit
brute_force_distance(points, (0.5,0.5))
brute_force_distance(points, (0.0,0.0))
brute_force_distance(points, (0.25,0.25))
%%timeit
tree.query(np.array([(0.5,0.5), (0.0,0.0), (0.25,0.25)]))
%%timeit
brute_force_distance(more_points, (0.5,0.5))
# brute_force_distance(more_points, (0.0,0.0))
# brute_force_distance(more_points, (0.25,0.25))
%%timeit
big_tree.query(np.array([(0.5,0.5), (0.0,0.0), (0.25,0.25)]))