# 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#

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

Tutorial

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