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

)¶

## Spatial Transformations¶

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

submodule.

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

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

See also

## Simplex representation¶

The simplices (triangles, tetrahedra, …) appearing in the Delaunay tessellation (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], :] # 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 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. |