Spatial algorithms and data structures (scipy.spatial)#

Spatial transformations#

These are contained in thescipy.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#

Distance metrics are contained in thescipy.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

See also

Tutorial

Simplex representation#

The simplices (triangles, tetrahedra, etc.) appearing in the Delaunaytessellation (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 simplextess.points[tess.simplices[i,j],:]# tessellation elementhull.points[hull.simplices[i,j],:]# convex hull facetvoro.vertices[voro.ridge_vertices[i,j],:]# ridge between Voronoi cells

For Delaunay triangulations and convex hulls, the neighborhoodstructure of the simplices satisfies the condition:tess.neighbors[i,j] is the neighboring simplex of the ithsimplex, opposite to thej-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 correspondto the convex hull facets on the corresponding N+1-Dparaboloid.

The Delaunay triangulation objects offer a method for locating thesimplex containing a given point, and barycentric coordinatecomputations.

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 inscipy.spatial#

QhullError

Raised when Qhull encounters an error condition, such as geometrical degeneracy when options to resolve are not enabled.