[ANN] DelaunayTriangulation.jl

Package Announcements
,
1

Hi all,

I have just released my package DelaunayTriangulation.jl for computing Delaunay triangulations of points in \mathbb R^2. The package makes use of the great package ExactPredicates.jl for the geometric predicates, thus making the code robust. Currently only unconstrained triangulations are supported, but I hope to eventually get to constrained triangulations (e.g. with the algorithm here). Code for Voronoi tessellations is currently in the package, although not as supported as the triangulation algorithms.

There are four methods available for computing a triangulation:

  • Using de Berg’s method, triangulate_berg, where points are added one at a time and the Delaunay property is restored by edge flips.
  • Using the Bowyer-Watson algorithm, triangulate_bowyer, where points are added one at a time and triangles are deleted when they contain the point in its circumdisk, adding new triangles to fill in the remaining cavity and restoring the Delaunay property.
  • A structured triangulation is provided for triangulations of points on a lattice, see triangulate_structured.
  • Gmsh support is also provided (tested only on Windows currently) using generate_mesh. (See also triangulate.)

More detail is provided in the README of the package, as are more examples, but below is a quick example using the Bowyer-Watson algorithm to triangulate a given set of points.

using StaticArraysCore
p1 = SVector{2, Float64}([0.0, 1.0])
p2 = SVector{2, Float64}([3.0, -1.0])
p3 = SVector{2, Float64}([2.0, 0.0])
p4 = SVector{2, Float64}([-1.0, 2.0])
p5 = SVector{2, Float64}([4.0, 2.0])
p6 = SVector{2, Float64}([-2.0, -1.0])
pts = [p1, p2, p3, p4, p5, p6]
T, adj, adj2v, DG = triangulate_bowyer(pts)

T is the set of elements, adj is the map which maps an edge to a vertex that together form a triangle in T, adj2v maps a point to all other edges that together form triangles in T surrounding the point, and DG is a graph that gives the neighbours of a given point. You can also extract convex hulls from these structures:

ch = convex_hull(DG, pts)

The points don’t have to be SVectors, any coordinate type is valid as long as it implements getx and gety (see the Customisation section of the README).

Also, if you are interested, some of the thought that went into the development of the code is given in a .pdf I wrote for Delaunay triangulations: see here.

Feedback and thoughts welcome!
Thanks,
Daniel.

12 Likes