# \[ANN\] DelaunayTriangulation.jl

**URL:** https://discourse.julialang.org/t/ann-delaunaytriangulation-jl/91239
**Category:** Package Announcements
**Tags:** package, announcement
**Created:** [December 5, 2022, 1:43am UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-jl/91239 "2022-12-05T01:43:35Z")
**Posts on this page:** 1
**Page:** 1

<div class="post-metadata">

### Author: ![DanielVandH](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielvandh/32/31134_2.png) [@DanielVandH](https://discourse.julialang.org/u/DanielVandH)
#### Post date: [December 5, 2022, 1:43am UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-jl/91239/1 "2022-12-05T01:43:35Z")

</div>

Hi all,

I have just released my package [DelaunayTriangulation.jl](https://github.com/DanielVandH/DelaunayTriangulation.jl) for computing Delaunay triangulations of points in \mathbb R^2. The package makes use of the great package [ExactPredicates.jl](https://github.com/lairez/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](https://doi.org/10.1016/j.comgeo.2015.04.006)). 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.

```julia
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:

```julia
ch = convex_hull(DG, pts)

```

The points don’t have to be `SVector`s, 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](https://github.com/DanielVandH/DelaunayTriangulation.jl/blob/main/DelaunayTriangulation.pdf).

Feedback and thoughts welcome!  
Thanks,  
Daniel.