Delaunay(points, furthest_site=False, incremental=False, qhull_options=None)
Delaunay tessellation in N dimensions.
.. versionadded:: 0.9
Parameters ---------- points : ndarray of floats, shape (npoints, ndim) Coordinates of points to triangulate furthest_site : bool, optional Whether to compute a furthest-site Delaunay triangulation. Default: False
.. versionadded:: 0.12.0 incremental : bool, optional Allow adding new points incrementally. This takes up some additional resources. qhull_options : str, optional Additional options to pass to Qhull. See Qhull manual for details. Option 'Qt' is always enabled. Default:'Qbb Qc Qz Qx Q12' for ndim > 4 and 'Qbb Qc Qz Q12' otherwise. Incremental mode omits 'Qz'.
.. versionadded:: 0.12.0
Attributes ---------- points : ndarray of double, shape (npoints, ndim) Coordinates of input points. simplices : ndarray of ints, shape (nsimplex, ndim+1) Indices of the points forming the simplices in the triangulation. For 2-D, the points are oriented counterclockwise. neighbors : ndarray of ints, shape (nsimplex, ndim+1) Indices of neighbor simplices for each simplex. The kth neighbor is opposite to the kth vertex. For simplices at the boundary, -1 denotes no neighbor. equations : ndarray of double, shape (nsimplex, ndim+2) normal, offset forming the hyperplane equation of the facet on the paraboloid (see `Qhull documentation <http://www.qhull.org/>`__ for more). paraboloid_scale, paraboloid_shift : float Scale and shift for the extra paraboloid dimension (see `Qhull documentation <http://www.qhull.org/>`__ for more). transform : ndarray of double, shape (nsimplex, ndim+1, ndim) Affine transform from ``x`` to the barycentric coordinates ``c``. This is defined by::
T c = x - r
At vertex ``j``, ``c_j = 1`` and the other coordinates zero.
For simplex ``i``, ``transformi,:ndim,:ndim`` contains inverse of the matrix ``T``, and ``transformi,ndim,:`` contains the vector ``r``.
If the simplex is degenerate or nearly degenerate, its barycentric transform contains NaNs. vertex_to_simplex : ndarray of int, shape (npoints,) Lookup array, from a vertex, to some simplex which it is a part of. If qhull option 'Qc' was not specified, the list will contain -1 for points that are not vertices of the tessellation. convex_hull : ndarray of int, shape (nfaces, ndim) Vertices of facets forming the convex hull of the point set. The array contains the indices of the points belonging to the (N-1)-dimensional facets that form the convex hull of the triangulation.
.. note::
Computing convex hulls via the Delaunay triangulation is inefficient and subject to increased numerical instability. Use `ConvexHull` instead. coplanar : ndarray of int, shape (ncoplanar, 3) Indices of coplanar points and the corresponding indices of the nearest facet and the nearest vertex. Coplanar points are input points which were *not* included in the triangulation due to numerical precision issues.
If option 'Qc' is not specified, this list is not computed.
.. versionadded:: 0.12.0 vertices Same as `simplices`, but deprecated. vertex_neighbor_vertices : tuple of two ndarrays of int; (indptr, indices) Neighboring vertices of vertices. The indices of neighboring vertices of vertex `k` are ``indicesindptr[k]:indptr[k+1]``. furthest_site True if this was a furthest site triangulation and False if not.
.. versionadded:: 1.4.0
Raises ------ QhullError Raised when Qhull encounters an error condition, such as geometrical degeneracy when options to resolve are not enabled. ValueError Raised if an incompatible array is given as input.
Notes ----- The tessellation is computed using the Qhull library `Qhull library <http://www.qhull.org/>`__.
.. note::
Unless you pass in the Qhull option 'QJ', Qhull does not guarantee that each input point appears as a vertex in the Delaunay triangulation. Omitted points are listed in the `coplanar` attribute.
Examples -------- Triangulation of a set of points:
>>> points = np.array([0, 0], [0, 1.1], [1, 0], [1, 1]) >>> from scipy.spatial import Delaunay >>> tri = Delaunay(points)
We can plot it:
>>> import matplotlib.pyplot as plt >>> plt.triplot(points:,0, points:,1, tri.simplices) >>> plt.plot(points:,0, points:,1, 'o') >>> plt.show()
Point indices and coordinates for the two triangles forming the triangulation:
>>> tri.simplices array([2, 3, 0], # may vary
[3, 1, 0], dtype=int32)
Note that depending on how rounding errors go, the simplices may be in a different order than above.
>>> pointstri.simplices array([[ 1. , 0. ], # may vary
[ 1. , 1. ],
[ 0. , 0. ]],
[[ 1. , 1. ],
[ 0. , 1.1],
[ 0. , 0. ]])
Triangle 0 is the only neighbor of triangle 1, and it's opposite to vertex 1 of triangle 1:
>>> tri.neighbors1 array(-1, 0, -1, dtype=int32) >>> pointstri.simplices[1,1] array( 0. , 1.1)
We can find out which triangle points are in:
>>> p = np.array((0.1, 0.2), (1.5, 0.5), (0.5, 1.05)) >>> tri.find_simplex(p) array( 1, -1, 1, dtype=int32)
The returned integers in the array are the indices of the simplex the corresponding point is in. If -1 is returned, the point is in no simplex. Be aware that the shortcut in the following example only works corretcly for valid points as invalid points result in -1 which is itself a valid index for the last simplex in the list.
>>> p_valids = np.array((0.1, 0.2), (0.5, 1.05)) >>> tri.simplicestri.find_simplex(p_valids) array([3, 1, 0], # may vary
[3, 1, 0], dtype=int32)
We can also compute barycentric coordinates in triangle 1 for these points:
>>> b = tri.transform1,:2.dot(np.transpose(p - tri.transform1,2)) >>> np.c_np.transpose(b), 1 - b.sum(axis=0) array([ 0.1 , 0.09090909, 0.80909091],
[ 1.5 , -0.90909091, 0.40909091],
[ 0.5 , 0.5 , 0. ])
The coordinates for the first point are all positive, meaning it is indeed inside the triangle. The third point is on a vertex, hence its null third coordinate.