Spatial algorithms and data structures (`scipy.spatial`)#

Spatial transformations#

These are contained in the scipy.spatial.transform submodule.

Nearest-neighbor queries#

`KDTree`(data[, leafsize, compact_nodes, ...])	kd-tree for quick nearest-neighbor lookup.
`cKDTree`(data[, leafsize, compact_nodes, ...])	kd-tree for quick nearest-neighbor lookup
`Rectangle`(maxes, mins)	Hyperrectangle class.

Distance metrics are contained in the scipy.spatial.distance submodule.

Delaunay triangulation, convex hulls, and Voronoi diagrams#

`Delaunay`(points[, furthest_site, ...])	Delaunay tessellation in N dimensions.
`ConvexHull`(points[, incremental, qhull_options])	Convex hulls in N dimensions.
`Voronoi`(points[, furthest_site, ...])	Voronoi diagrams in N dimensions.
`SphericalVoronoi`(points[, radius, center, ...])	Voronoi diagrams on the surface of a sphere.
`HalfspaceIntersection`(halfspaces, interior_point)	Halfspace intersections in N dimensions.

Plotting helpers#

`delaunay_plot_2d`(tri[, ax])	Plot the given Delaunay triangulation in 2-D
`convex_hull_plot_2d`(hull[, ax])	Plot the given convex hull diagram in 2-D
`voronoi_plot_2d`(vor[, ax])	Plot the given Voronoi diagram in 2-D

Simplex representation#

The simplices (triangles, tetrahedra, etc.) appearing in the Delaunay tessellation (N-D simplices), convex hull facets, and Voronoi ridges (N-1-D 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 ith 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-D paraboloid.

The Delaunay triangulation objects offer a method for locating the simplex containing a given point, and barycentric coordinate computations.

Functions#

`tsearch`(tri, xi)	Find simplices containing the given points.
`distance_matrix`(x, y[, p, threshold])	Compute the distance matrix.
`minkowski_distance`(x, y[, p])	Compute the L**p distance between two arrays.
`minkowski_distance_p`(x, y[, p])	Compute the pth power of the L**p distance between two arrays.
`procrustes`(data1, data2)	Procrustes analysis, a similarity test for two data sets.
`geometric_slerp`(start, end, t[, tol])	Geometric spherical linear interpolation.

Warnings / Errors used in `scipy.spatial`#

QhullError

scipy.sparse.csgraph.reconstruct_path

scipy.spatial.KDTree

Spatial algorithms and data structures (scipy.spatial)#