#### Previous topic

scipy.sparse.csgraph.reconstruct_path

#### Next topic

scipy.spatial.KDTree

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

## Nearest-neighbor Queries¶

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

## Delaunay Triangulation, Convex Hulls and Voronoi Diagrams¶

 Delaunay(points[, furthest_site, ...]) Delaunay tesselation 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

Tutorial

## Simplex representation¶

The simplices (triangles, tetrahedra, ...) appearing in the Delaunay tesselation (N-dim simplices), convex hull facets, and Voronoi ridges (N-1 dim simplices) are represented in the following scheme:

tess = Delaunay(points)
hull = ConvexHull(points)
voro = Voronoi(points)

# coordinates of the j-th vertex of the i-th simplex
tess.points[tess.simplices[i, j], :]        # tesselation 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¶

 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 p-th power of the L**p distance between two arrays. procrustes(data1, data2) Procrustes analysis, a similarity test for two data sets.