SciPy

This is documentation for an old release of SciPy (version 0.16.0). Read this page in the documentation of the latest stable release (version 1.15.1).

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

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.

Plotting Helpers

delaunay_plot_2d(tri[, ax]) Plot the given Delaunay triangulation in 2-D :Parameters: tri : scipy.spatial.Delaunay instance Triangulation to plot ax : matplotlib.axes.Axes instance, optional Axes to plot on :Returns: fig : matplotlib.figure.Figure instance Figure for the plot ..
convex_hull_plot_2d(hull[, ax]) Plot the given convex hull diagram in 2-D :Parameters: hull : scipy.spatial.ConvexHull instance Convex hull to plot ax : matplotlib.axes.Axes instance, optional Axes to plot on :Returns: fig : matplotlib.figure.Figure instance Figure for the plot ..
voronoi_plot_2d(vor[, ax]) Plot the given Voronoi diagram in 2-D :Parameters: vor : scipy.spatial.Voronoi instance Diagram to plot ax : matplotlib.axes.Axes instance, optional Axes to plot on :Returns: fig : matplotlib.figure.Figure instance Figure for the plot ..

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.