Delaunay triangulation for a set of points.
Computes the Delaunay triangulation, which connects points such that no point is inside the circumcircle of any triangle. This is useful for interpolation, mesh generation, and computing Voronoi diagrams.
The triangulation is built by incremental insertion (Bowyer–Watson) over ghost triangles that stand for the unbounded region beyond each hull edge, so no finite super-triangle can distort the hull. Every triangle is counter-clockwise, which is what makes the in-circle determinant's sign meaningful.
Examples
points = [{0, 0}, {100, 0}, {50, 100}, {25, 50}, {75, 50}]
delaunay = Visualize.Geo.Delaunay.new(points)
# Get triangles (each is [i, j, k] indices)
triangles = Visualize.Geo.Delaunay.triangles(delaunay)
# Find which triangle contains a point
i = Visualize.Geo.Delaunay.find(delaunay, {30, 30})
# Get neighbors of a point
neighbors = Visualize.Geo.Delaunay.neighbors(delaunay, 0)Summary
Functions
Finds the triangle containing the given point, returns triangle index or -1
Returns the convex hull as point indices
Returns the indices of points neighboring the given point
Creates a new Delaunay triangulation from points.
Returns the points
Generates SVG path data for the convex hull
Generates SVG path data for all triangle edges
Returns the triangles as lists of point indices
Types
@type t() :: %Visualize.Geo.Delaunay{ halfedges: [integer()], hull: [non_neg_integer()], points: [point()], triangles: [non_neg_integer()] }
Functions
Finds the triangle containing the given point, returns triangle index or -1
@spec hull(t()) :: [non_neg_integer()]
Returns the convex hull as point indices
@spec neighbors(t(), non_neg_integer()) :: [non_neg_integer()]
Returns the indices of points neighboring the given point
Creates a new Delaunay triangulation from points.
triangles holds three point indices per triangle, counter-clockwise; halfedges[e]
is the index of the half-edge opposite half-edge e (3t + k runs from
triangles[3t + k] to triangles[3t + (k + 1) rem 3]) or -1 on the hull; hull
lists the convex hull counter-clockwise from the leftmost point. Coincident points
after the first are left out of the triangulation.
Returns the points
Generates SVG path data for the convex hull
Generates SVG path data for all triangle edges
@spec triangles(t()) :: [[non_neg_integer()]]
Returns the triangles as lists of point indices