Spatial algorithms and data structures (scipy.spatial)¶
|KDTree(data[, leafsize])||kd-tree for quick nearest-neighbor lookup|
|cKDTree||kd-tree for quick nearest-neighbor lookup|
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.|
|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|
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.
|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.|