DelaunayTriangulation

This is a package for constructing Delaunay triangulations and Voronoi tessellations of planar point sets. Supports unconstrained and constrained triangulations, mesh refinement, Voronoi tessellations, and clipped and centroidal Voronoi tessellations. All geometric predicates are computed via ExactPredicates.jl. Many features are available, some of these being:

• Unconstrained and constrained triangulations. Support is provided for many types of domains, as given in the docs.
• Computation of Voronoi tessellations, including clipping of polygons to the convex hull. I hope to get this working for constrained triangulations, but it's difficult.
• Computation of centroidal Voronoi tessellations using Lloyd's algorithm.
• Mesh refinement, with support for custom angle and area constraints.
• Geometric predicates are implemented with ExactPredicates.jl, and many predicates have been extended from ExactPredicates.jl.
• Dynamic point insertion, point deletion, and segment insertion, amongst many other operations.
• Computation of convex hulls, either from the triangulation itself or using the monotone chain algorithm.
• Triangulation of convex polygons.
• Efficient point location on convex geometries, even with interior holes. Partial support exists for non-convex geometries, although it is much slower and not perfect.
• Computation of the pole of inaccessibility, i.e. the point in a polygon that is furthest from a boundary (see e.g. this blogpost).
• Fully customisable interface for defining geometric primitives.
• Simple iteration over mesh elements, including points, edges, or triangles.
• Computation of statistics over individual triangular elements and over a complete triangulation.

Much of the work in this package is derived from the book Delaunay Mesh Generation by Cheng, Dey, and Shewchuk (2013). Feel free to use the issues tab for any suggestions, feedback, or if you have any questions about using the package, internals, etc.

Quick Example

See the docs for plenty of examples. For now, here are some small examples.

using DelaunayTriangulation, CairoMakie, StableRNGs

fig = Figure(fontsize=24)

## Unconstrained example: Just some random points 
rng = StableRNG(2)
pts = randn(rng, 2, 500)
tri = triangulate(pts; rng)
ax = Axis(fig[1, 1], title = "(a): Unconstrained", titlealign = :left, width=400,height=400)
triplot!(ax, tri) 

## Constrained example: Generate some points, convert to indices, triangulate 
points = [(0.0, 0.0), (1.0, 0.0), (1.0, 0.3), (0.8, 0.3), 
(0.8, 0.5), (1.0, 0.5), (1.0, 1.0), (0.0, 1.0), (0.0, 0.0)]
boundary_nodes, points = convert_boundary_points_to_indices(points)
edges = Set(((2, 8), (5, 7)))
tri = triangulate(points; boundary_nodes, edges, rng)
ax = Axis(fig[1, 2], title = "(b): Constrained, pre-refinement", titlealign = :left, width=400,height=400)
triplot!(ax, tri)

## Dynamic updating 
n = num_points(tri)
add_point!(tri, (0.2, 0.2); rng)
add_point!(tri, (0.8, 0.8); rng)
add_point!(tri, (0.3, 0.2); rng)
add_point!(tri, (0.6, 0.2); rng)
add_point!(tri, (0.3, 0.3); rng)
add_edge!(tri, (n+1, n+4); rng)
delete_point!(tri, n+2; rng)
ax = Axis(fig[1, 3], title = "(c): Updated constrained, pre-refinement", titlealign = :left, width=400,height=400)
triplot!(ax, tri)

## Refinement example
A = get_total_area(tri)
refine!(tri; max_area = 1e-2A, min_angle = 28.7, rng)
ax = Axis(fig[1, 4], title = "(d): Constrained, post-refinement", titlealign = :left, width=400,height=400)
triplot!(ax, tri, show_convex_hull = false)

## Constrained example with holes
outer_boundary = [[(0.0, 0.0), (1.0, 0.0), (1.0, 0.3), (0.8, 0.3), 
(0.8, 0.5), (1.0, 0.5), (1.0, 1.0), (0.0, 1.0), (0.0, 0.0)]]
inner_boundary = [[(0.2, 0.2), (0.2, 0.6), (0.4, 0.6), (0.4, 0.2), (0.2, 0.2)]]
boundary_nodes, points = convert_boundary_points_to_indices([outer_boundary, inner_boundary])
edges = Set(((2, 8), (5, 7)))
tri = triangulate(points; boundary_nodes, edges, rng)
A = get_total_area(tri)
refine!(tri; max_area = 1e-3A, min_angle = 31.5, rng)
ax = Axis(fig[2, 1], title = "(e): Multiply-connected", titlealign = :left, width=400,height=400)
triplot!(ax, tri, show_convex_hull = false)

## Voronoi tessellation: Make tessellations from their dual triangulation
pts = 25randn(rng, 2, 500)
tri = triangulate(pts; rng)
vorn = voronoi(tri)
ax = Axis(fig[2, 2], title = "(f): Voronoi tessellation", titlealign = :left, width=400,height=400)
voronoiplot!(ax, vorn, show_generators = false) 
xlims!(ax, -120, 120); ylims!(ax, -120, 120)

## Clipped Voronoi tessellation 
vorn = voronoi(tri, true)
cmap = cgrad(:jet)
colors = get_polygon_colors(vorn, cmap)
ax = Axis(fig[2, 3], title = "(g): Clipped Voronoi tessellation", titlealign = :left, width=400,height=400)
voronoiplot!(ax, vorn, show_generators = false, polygon_color = colors)

## Centroidal Voronoi tessellation (CVT)
points = [(0.0,0.0),(1.0,0.0),(1.0,1.0),(0.0,1.0)]
tri = triangulate(points; boundary_nodes = [1,2,3,4,1], rng)
refine!(tri; max_area=1e-3, min_angle = 29.871, rng)
vorn = voronoi(tri)
smooth_vorn = centroidal_smooth(vorn; maxiters = 2500)
cmap = cgrad(:matter)
colors = get_polygon_colors(smooth_vorn, cmap)
ax = Axis(fig[2, 4], title = "(h): Centroidal Voronoi tessellation", titlealign = :left, width=400,height=400)
voronoiplot!(ax, smooth_vorn, show_generators = true, markersize=4, polygon_color = colors)

resize_to_layout!(fig)
fig

Animations

Just as a nice demonstration of the incremental behaviour of the algorithms in this package, here's an example of how we build a triangulation of the Julia logo.

Here is also a nice animation showing the computation of a centroidal Voronoi tessellation.

Similar Packages

This is not the only Delaunay triangulation package available. Some others are:

• VoronoiDelaunay.jl: A pure Julia library that constructs planar triangulations and tessellations like in this package, although no support for constrained triangulations / mesh refinement or clipped / centroid tessellations. Restricts points to $[1, 2] \times [1, 2]$.
• VoronoiCells.jl: A pure Julia library that extends VoronoiDelaunay.jl. This package provides useful tools for constructing and working with Voronoi tessellations. Supports clipping Voronoi cells to a specified rectangle. Like VoronoiDelaunay.jl, restricts points to $[1, 2] \times [1, 2]$.
• Delaunay.jl: Wraps Python's main Delaunay triangulation library, scipy.spatial.Delaunay, for computing Delaunay triangulations in $\mathbb R^N$. I don't believe constrained triangulations or mesh refinement is available here.
• MiniQhull.jl: Wraps Qhull for computing unconstrained Delaunay triangulations in $\mathbb R^N$. No support is provided for mesh refinement.
• DirectQhull.jl: Similar to MiniQhull.jl, although also provides support for convex hulls and Voronoi tessellations from Qhull.
• Delaunator.jl: A pure Julia library modelled after the JavaScript Delaunator library. This package can construct unconstrained triangulations of planar point sets. No support is available for constrained triangulations or mesh refinement, although support exists for computing the dual Voronoi tessellation. Centroidal tessellations are not implemented, although the Voronoi cells can be clipped to a bounding box.
• TriangleMesh.jl, Triangulate.jl, Triangle.jl: Interfaces to Shewchuk's Triangle library.
• TetGen.jl: This is for Delaunay tetrahedralisation, wrapping TetGen.