### Table Of Contents

- Spatial algorithms and data structures (`scipy.spatial`)
  - Nearest-neighbor Queries
  - Delaunay Triangulation, Convex Hulls and Voronoi Diagrams
  - Plotting Helpers
  - Simplex representation
    - Functions

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

See also

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.