Generates the Delaunay triangulation of a set of points.
Generates the Delaunay triangulation of a set of points.
The DelaunayTriangulation class operates on a collection of Coordinates to
produce the unique triangulation (after projecting the points to the x-y
plane) that satisfies the condition of each triangle in the result having a
circumscribing circle where no vertices of the input point set are in the
interior of that circle.
Note that the input set must have 2 or more distinct points. Collinear points
are allowed.
Whenever using this class for complex tasks with large quantities of points,
numerical issues must be considered. First, this triangulator will pare down
the input set so as to remove points which are not numerically distinct. This
may result in points which are not strictly equal, but indistinguishable from
one another with respect to the geometric predicates (collinearity tests,
in-circle tests, orientation tests). Failure to understand and address
potential numerical issues in your data *may cause infinite loops*! (It is
our experience that sufficiently large point sets will eventually run afoul of
these problems if left alone.) The /tolerance/ parameter is set to a
reasonable value in the defaults of the DelaunayTriangulation object's apply()
method, but bear in mind that problems may arise in your particular case.
Generates the Delaunay triangulation of a set of points.
The DelaunayTriangulation class operates on a collection of Coordinates to produce the unique triangulation (after projecting the points to the x-y plane) that satisfies the condition of each triangle in the result having a circumscribing circle where no vertices of the input point set are in the interior of that circle.
Note that the input set must have 2 or more distinct points. Collinear points are allowed.
Whenever using this class for complex tasks with large quantities of points, numerical issues must be considered. First, this triangulator will pare down the input set so as to remove points which are not numerically distinct. This may result in points which are not strictly equal, but indistinguishable from one another with respect to the geometric predicates (collinearity tests, in-circle tests, orientation tests). Failure to understand and address potential numerical issues in your data *may cause infinite loops*! (It is our experience that sufficiently large point sets will eventually run afoul of these problems if left alone.) The /tolerance/ parameter is set to a reasonable value in the defaults of the DelaunayTriangulation object's apply() method, but bear in mind that problems may arise in your particular case.