Import std.algo.delaunay
std.algo.delaunay
Delaunay triangulation and Voronoi diagrams of points in 2D, and Lloyd relaxation, which moves points apart until they're evenly spread, for maps, meshes, and placing things. The Delaunay triangles are those whose circumcircles hold none of the points, which keeps them as near equilateral as the points allow; a point's Voronoi cell is where's nearer it than any other. The math is in Doubles, with Shewchuk's exact predicates, so points however near each other give a triangulation. The triangulation is Bowyer and Watson's, a point at a time in order of x then y, with a point at infinity whose triangles are the hull's outside, so the hull comes out whole; points on one circle are triangulated by the order they come in.
std/algo/delaunay.fb
Functions
Delaunay
function
@PanicsAtCaller Public Function Delaunay(points: Vec2[]): (Int, Int, Int)[]The Delaunay triangulation of the points: triangles whose circumcircles hold none of the
points, each as the indices of its corners in points, counterclockwise. Fewer than three
points, or points all on a line, have none, and of points that are equal, only the first
is a corner. A coordinate that's infinite or NaN panics.
Voronoi
function
@PanicsAtCaller Public Function Voronoi(points: Vec2[], bounds: Rect): Vec2[][]Each point's Voronoi cell inside bounds: the polygon, counterclockwise, with no corner twice
in a row, of where in bounds is no nearer another point, and empty for a point whose cell is
outside bounds or only touches them, at a corner or along an edge. Points that are equal share
a cell, and fewer than two points have bounds' whole rectangle for theirs. A coordinate
that's infinite or NaN, or bounds that aren't finite or have a negative size, panic.
LloydRelax
function
@PanicsAtCaller Public Function LloydRelax(points: Vec2[], bounds: Rect, iterations: Int = 1): Vec2[]The points moved, iterations times, each to the middle of its Voronoi cell in bounds,
which spreads them evenly: Lloyd's relaxation. A point whose cell is empty stays. A negative
number of iterations, a coordinate that's infinite or NaN, or bounds that aren't finite or
have a negative size, panics.
Report an issue with this page or with FutureBlitz on GitHub.