Spatial algorithms and data structures (scipy.spatial
)¶
Spatial Transformations¶
These are contained in the scipy.spatial.transform
submodule.
Nearestneighbor Queries¶

kdtree for quick nearestneighbor lookup 

kdtree for quick nearestneighbor lookup 

Hyperrectangle class. 
Distance metrics are contained in the scipy.spatial.distance
submodule.
Delaunay Triangulation, Convex Hulls and Voronoi Diagrams¶

Delaunay tessellation in N dimensions. 

Convex hulls in N dimensions. 

Voronoi diagrams in N dimensions. 

Voronoi diagrams on the surface of a sphere. 

Halfspace intersections in N dimensions. 
Plotting Helpers¶

Plot the given Delaunay triangulation in 2D 

Plot the given convex hull diagram in 2D 

Plot the given Voronoi diagram in 2D 
See also
Simplex representation¶
The simplices (triangles, tetrahedra, …) appearing in the Delaunay tessellation (Ndim simplices), convex hull facets, and Voronoi ridges (N1 dim simplices) are represented in the following scheme:
tess = Delaunay(points)
hull = ConvexHull(points)
voro = Voronoi(points)
# coordinates of the jth vertex of the ith simplex
tess.points[tess.simplices[i, j], :] # tessellation element
hull.points[hull.simplices[i, j], :] # convex hull facet
voro.vertices[voro.ridge_vertices[i, j], :] # ridge between Voronoi cells
For Delaunay triangulations and convex hulls, the neighborhood
structure of the simplices satisfies the condition:
tess.neighbors[i,j]
is the neighboring simplex of the i
th
simplex, opposite to the j
vertex. It is 1 in case of no neighbor.
Convex hull facets also define a hyperplane equation:
(hull.equations[i,:1] * coord).sum() + hull.equations[i,1] == 0
Similar hyperplane equations for the Delaunay triangulation correspond to the convex hull facets on the corresponding N+1 dimensional paraboloid.
The Delaunay triangulation objects offer a method for locating the simplex containing a given point, and barycentric coordinate computations.
Functions¶

Find simplices containing the given points. 

Compute the distance matrix. 

Compute the L**p distance between two arrays. 

Compute the pth power of the L**p distance between two arrays. 

Procrustes analysis, a similarity test for two data sets. 