HMath.Geometry.Triangulation¶
Module index · Numerical conventions
Description
Deterministic Bowyer-Watson Delaunay triangulation (at most 256 unique points), edge-flip constrained Delaunay triangulation, polygon ear clipping, and bounded Voronoi cells. Triangles use original zero-based point indices and counterclockwise orientation. Collinear clouds return no triangles. Constraints must be noncrossing input-vertex segments with no interior input vertices; they do not specify holes or discard the outer convex hull. Exact Rational orientation/incircle signs avoid epsilon topology decisions.
On this page¶
| API | Purpose |
|---|---|
| IndexedTriangle | Counterclockwise indices into the caller's input point list. |
| delaunay | Incremental cavity replacement. |
| constrainedDelaunay | Insert noncrossing constrained edges by convex quadrilateral flips, then Lawson-flip every unconstrained illegal edge. |
| voronoi | Voronoi cells clipped to an ordered nonzero rectangle, one polygon ring per site (empty only if the site lies outside the clipping rectangle). |
| earClip | Ear clipping of a simple polygon. |
Documentation
IndexedTriangle
type IndexedTriangle = (Int, Int, Int) Source #
Counterclockwise indices into the caller's input point list.
delaunay
delaunay :: [Point2] -> Either MathError [IndexedTriangle] Source #
Incremental cavity replacement. Cocircular insertion uses a strict in-circle predicate, giving a deterministic (not unique) valid diagonal.
constrainedDelaunay
constrainedDelaunay :: [Point2] -> [(Int, Int)] -> Either MathError [IndexedTriangle] Source #
Insert noncrossing constrained edges by convex quadrilateral flips, then Lawson-flip every unconstrained illegal edge. Work is bounded explicitly.
voronoi
voronoi :: Rectangle -> [Point2] -> Either MathError [[Point2]] Source #
Voronoi cells clipped to an ordered nonzero rectangle, one polygon ring per site (empty only if the site lies outside the clipping rectangle). Direct pairwise half-plane clipping is O(n^3), limited to 128 sites. Bisector classification and intersections use exact Rational arithmetic; final vertices are rounded once to Double.