Spatial tessellation
Partitioning 2D or higher-dimensional point clouds into simplices for geometric analysis.
SciPy · Class
spatial.Delaunay
scipy.spatial.Delaunay computes a Delaunay tessellation in N dimensions from point coordinates. It supports furthest-site and incremental construction plus custom Qhull options.
- Since
- 0.9
How it works
Delaunay constructs an N-dimensional tessellation from an array of point coordinates using Qhull. The resulting object exposes the simplices and related geometry, while optional settings support furthest-site triangulation, incremental point insertion, and custom Qhull behavior.
Syntax
scipy.spatial.Delaunay(points, furthest_site=False, incremental=False, qhull_options=None)Parameters
| Name | Type | Description |
|---|---|---|
points | ndarray of floats | Coordinates of points to triangulate; an ndarray of floats with shape (npoints, ndim). |
furthest_site | bool, optional | Whether to compute a furthest-site Delaunay triangulation. |
incremental | bool, optional | Allow adding new points incrementally; this consumes additional resources. |
qhull_options | str, optional | Additional options passed to Qhull. Qt is always enabled. |
Returns
A Delaunay tessellation object containing the computed triangulation and its geometric data.
Key points
- The class creates a Delaunay tessellation for points in any supported number of dimensions.
- points supplies the coordinates as a floating-point array with shape (npoints, ndim).
- furthest_site selects the furthest-site variant when set to True.
- incremental enables adding points after the initial tessellation is built.
- qhull_options lets callers provide extra Qhull configuration flags.
- SciPy always enables Qhull's Qt option, regardless of the supplied option string.
Common mistakes
- Some input points may be omitted as vertices; use the Qhull QJ option when that guarantee is required.
- Incremental mode uses extra resources, so enable it only when adding points after construction is necessary.
- The default Qhull option set differs in incremental mode because Qz is omitted.
Example: Triangulate points
import numpy as np
from scipy.spatial import Delaunay
points = np.array([[0, 0], [0, 1.1], [1, 0], [1, 1]])
tri = Delaunay(points)
print(tri.simplices)Construct a two-dimensional Delaunay triangulation and print the point-index simplices that form it.
When to use it
Mesh generation
Building mesh connectivity from scattered coordinates.
Incremental geometry
Adding points to an existing triangulation without rebuilding from scratch.
Interview questions
QWhat does scipy.spatial.Delaunay construct?
Delaunay is a class that computes a tessellation in N dimensions from point coordinates. Its input is an ndarray shaped (npoints, ndim), and the computation uses Qhull.
Follow-up: How can the triangulation be made incremental? Construct it with incremental=True, accepting the additional resource cost documented for that mode.
QHow do you request a furthest-site triangulation?
Set furthest_site=True to compute a furthest-site Delaunay triangulation instead of the ordinary form. The parameter is optional and defaults to False.
Follow-up: What other construction-time behavior can be customized? qhull_options passes additional options to Qhull, while Qt remains enabled.
QWhat is the role of qhull_options?
qhull_options is a string of extra options passed to Qhull. If it is not supplied, SciPy uses a dimension-dependent default: Qbb Qc Qz Q12 normally, adding Qx when ndim is greater than four.
Follow-up: What changes for incremental construction? The documented default option set omits Qz in incremental mode.
Related
scipy.spatial.ConvexHullscipy.spatial.Voronoiscipy.spatial.KDTreescipy.spatial.cKDTree