# \[ANN\] DelaunayTriangulation v1.0: Curved domains and improved docs/code

**URL:** <https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997>\
**Category:** Package Announcements\
**Tags:** package, announcement\
**Created:** [May 8, 2024, 12:56pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997 "2024-05-08T12:56:10Z")\
**Posts on this page:** 14\
**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:** [May 8, 2024, 12:56pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/1 "2024-05-08T12:56:10Z")

</div>

Hi all,

I have recently released the first major version of my package [DelaunayTriangulation.jl](https://github.com/JuliaGeometry/DelaunayTriangulation.jl), a package for computing Delaunay triangulations and Voronoi tessellations in two dimensions. The most important new feature here is the ability to now triangulate and refine domains defined by curves rather than only piecewise linear boundaries. Thus, the package’s major features are now:

- Unconstrained and constrained triangulations.
- Mesh refinement, with support for generic constraints.
- Voronoi tessellations.
- Voronoi tessellations clipped to a rectangle or to the convex hull.
- Centroidal Voronoi tessellations.
- Triangulations of curve-bounded domains.

More features are listed in the README and in the [documentation](https://juliageometry.github.io/DelaunayTriangulation.jl/stable/). In addition to this new feature of curve-bounded domains, the documentation has been completely rewritten and should hopefully be a lot easier to navigate. I give some better examples of using the code, some example applications, and give better details of the mathematics involved.

The curves I provide support for are:

- `BSpline`
- `BezierCurve`
- `CircularArc`
- `CatmullRomSpline`
- `LineSegment`
- `EllipticalArc`

But you can also define your own; see the docstring for `DelaunayTriangulation.AbstractParametricCurve` or the docs.

Here is an example of triangulating and refining a domain defined by an annulus.

```julia
using DelaunayTriangulation
using CairoMakie 
R₁ = 1.0
R₂ = 2.0
outer_circle = CircularArc((R₂, 0.0), (R₂, 0.0), (0.0, 0.0))
inner_circle = CircularArc((R₁, 0.0), (R₁, 0.0), (0.0, 0.0), positive=false)
points = NTuple{2,Float64}[]
tri = triangulate(points; boundary_nodes=[[[outer_circle]], [[inner_circle]]])
A = 2π * (R₂^2 - R₁^2)
refine!(tri; max_area=2e-3A, min_angle=33.0)
fig, ax, sc = triplot(tri)
fig

```

![qTuczvg](https://global.discourse-cdn.com/julialang/original/3X/e/b/eb3d110928b7c5b6a275ab7b847c92d52ae30c98.png)

_If you want some more examples other than just those in the docs, I will soon be updating [FiniteVolumeMethod.jl](https://github.com/SciML/FiniteVolumeMethod.jl) to use these new curve-bounded domains rather than e.g. manually discretising a circle and triangulating that_

Many other improvements have been made. For example, you no longer need to do `check_args=false` for more complicated domains, as I have now implemented an automatic way for the package to check that your domain is valid even with nested domains and disjoint domains. The public API has now also been fully defined for the first time. See the full changelog [here](https://github.com/JuliaGeometry/DelaunayTriangulation.jl/blob/main/NEWS.md).

---

<div class="post-metadata">

**Author:** ![kylebeggs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kylebeggs/32/43348_2.png) [@kylebeggs](https://discourse.julialang.org/u/kylebeggs)\
**Post date:** [May 8, 2024, 1:21pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/2 "2024-05-08T13:21:26Z")

</div>

Cool to see this hit 1.0! Congrats! How hard would it be to extend this to 3D?

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [May 8, 2024, 1:24pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/3 "2024-05-08T13:24:18Z")

</div>

Thanks for this great contribution. The documentation is very well written.

---

<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:** [May 8, 2024, 1:31pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/4 "2024-05-08T13:31:29Z")

</div>

3D seems to be a much bigger challenge. I did at some point spend a few weeks trying to see if it could work easily. I got as far as making an unconstrained triangulator working, but the corner cases in 3D are so much more annoying that I gave up (2D is bad enough - just look at how long the [point location code](https://github.com/JuliaGeometry/DelaunayTriangulation.jl/blob/main/src/algorithms/point_location/jump_and_march.jl) is…). Not sure where that 3D code is now unfortunately. Another challenge is just in designing the data structures for working efficiently with 3D geometries, especially for constrained geometries. None of my work requires 3D triangulations unfortunately, else I probably would’ve kept trying.

The book I used for all this ([here](https://people.eecs.berkeley.edu/~jrs/meshbook.html)) has a lot of great discussion on 3D, and more general cases like triangulating on a surface. If someone wanted to take up the mantle and try and get a 3D code working, this book would be where I’d start. For now, I think TetGen.jl is probably the best to use in Julia? Never used it.

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [May 8, 2024, 1:56pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/5 "2024-05-08T13:56:25Z")

</div>

> [@DanielVandH](#):
>
> just look at how long the [point location code](https://github.com/JuliaGeometry/DelaunayTriangulation.jl/blob/main/src/algorithms/point_location/jump_and_march.jl) is…

I just want to say I love the level of detail in the docstrings ❤

---

<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:** [May 8, 2024, 3:18pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/6 "2024-05-08T15:18:46Z")

</div>

Thank you 🙂 I’ve tried to make most functions have detailed (enough) docstrings to make everything easier to understand, especially for internal functions incase anyone else wants to contribute to the package - rather than me being the only one with any idea what’s going on 😅

---

<div class="post-metadata">

**Author:** ![tecosaur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tecosaur/32/23206_2.png) [@tecosaur](https://discourse.julialang.org/u/tecosaur)\
**Post date:** [May 8, 2024, 3:27pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/7 "2024-05-08T15:27:18Z")

</div>

I love thorough docstrings, and IMO tricky internal functions are often _most_ direly in need of them.

**[Shameless self-promotion]** I’m actually working on a package to help check that all functions/structs/global variables have decent attached docstrings: [GitHub - tecosaur/CheckDoc.jl: Documentation linting](https://github.com/tecosaur/CheckDoc.jl/), it still needs more work before I’m ready to (more) publically announce it though.

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [May 9, 2024, 5:36am UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/8 "2024-05-09T05:36:43Z")

</div>

> [@tecosaur](#):
>
> **[Shameless self-promotion]**

Is there a GitHub shortcut to star every repo a user have ever written or ever will? That would save me some work with people like @Lilith and you

---

<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:** [May 11, 2024, 10:50am UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/9 "2024-05-11T10:50:22Z")

</div>

> [@DanielVandH](#):
>
> If you want some more examples other than just those in the docs, I will soon be updating [FiniteVolumeMethod.jl](https://github.com/SciML/FiniteVolumeMethod.jl) to use these new curve-bounded domains rather than e.g. manually discretising a circle and triangulating that

[FiniteVolumeMethod.jl](https://github.com/SciML/FiniteVolumeMethod.jl) has now been updated to now use curve-bounded domains where applicable. As an example of how you could use these new features to specify a mesh, here I specify an annulus where the outer circle has been split into two parts to allow for different boundary conditions on each part. Extra segments are added to define a perturbed interface so that the diffusivity is different on each side. This example comes from [this example](https://sciml.github.io/FiniteVolumeMethod.jl/dev/tutorials/mean_exit_time/#Adding-obstacles).

```julia
using DelaunayTriangulation, CairoMakie
# Some diffusion_parameters
R₁, R₂ = 2.0, 3.0 # perturbed interface radius, outer radius
ε = 0.05 # perturbation parameter for the perturbed interface
g = θ -> sin(3θ) + cos(5θ) # perturbation function
R1_f = let R₁ = R₁, ε = ε, g = g # use let for type stability
    θ -> R₁ * (1.0 + ε * g(θ))
end # interface radius function
ϵr = 0.25 # interior hole radius 
# Define the boundary: 
# 1. The boundary should be absorbing for most of it, 
# 2. but have a small reflecting arc on the outer circle,
# 3. and a small absorbing hole in the interior.
dirichlet = CircularArc((R₂ * cos(ϵr), R₂ * sin(ϵr)), (R₂ * cos(2π - ϵr), R₂ * sin(2π - ϵr)), (0.0, 0.0))
neumann = CircularArc((R₂ * cos(2π - ϵr), R₂ * sin(2π - ϵr)), (R₂ * cos(ϵr), R₂ * sin(ϵr)), (0.0, 0.0))
hole = CircularArc((0.0, 1.0), (0.0, 1.0), (0.0, 0.0), positive=false)
boundary_nodes = [[[dirichlet], [neumann]], [[hole]]]
points = [(-2.0, 0.0), (0.0, 2.95)] # also add small point holes that serve as obstacles 
tri = triangulate(points; boundary_nodes)
# Now add the perturbed interface. There is no capability for adding 
# curves that are not the boundary, so we need to do this manually.
θ = LinRange(0, 2π, 250)
xin = @views (@. R1_f(θ) * cos(θ))[begin:end-1]
yin = @views (@. R1_f(θ) * sin(θ))[begin:end-1]
add_point!(tri, xin[1], yin[1])
for i in 2:length(xin)
    add_point!(tri, xin[i], yin[i])
    n = DelaunayTriangulation.num_points(tri)
    add_segment!(tri, n - 1, n)
end
n = DelaunayTriangulation.num_points(tri)
add_segment!(tri, n - 1, n)
tri1 = deepcopy(tri) # for plotting after
refine!(tri; max_area=1e-3get_area(tri));
# Plot 
fig = Figure()
ax = Axis(fig[1, 1], width=400, height=400, title="Pre-refinement")
triplot!(ax, tri1)
ax = Axis(fig[1, 2], width=400, height=400, title="Post-refinement")
triplot!(ax, tri)
resize_to_layout!(fig)
fig

```

 ![KzZRS5N](https://global.discourse-cdn.com/julialang/original/3X/8/d/8db4d922a69e7a100f29be0d1242b055e63656d0.jpeg)

---

<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:** [July 28, 2024, 12:07pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/10 "2024-07-28T12:07:45Z")

</div>

Now that [AdaptivePredicates.jl](https://github.com/JuliaGeometry/AdaptivePredicates.jl) has been released, I’ve made it the default kernel for computing predicates in DelaunayTriangulation as of v1.1.0. This gives a significant improvement in performance (sometimes). We can now also give robust computations of triangle areas which has fixed some bugs. Moreover, since AdaptivePredicates.jl supports `Float32`, DelaunayTriangulation.jl now supports `Float32` without having to convert to `Float64` everywhere (unless the `ExactKernel()` is used).

Additionally, instead of forcing users to use ExactPredicates.jl or AdaptivePredicates.jl, `triangulate` (and `voronoi`, `refine!`, etc.) has a `predicates` keyword argument that you can use for specifying the kernels `FastKernel()`, `AdaptiveKernel()`, or `ExactKernel()`. The difference between these choices is described [here](https://juliageometry.github.io/DelaunayTriangulation.jl/dev/manual/predicate_kernels/).

Here is a quick example comparing the kernels applied to the triangulation of points on a lattice (meaning there are lots of collinear and cocircular points, pretty much the worst case scenario). Here, `FastKernel()` is not even likely to give a valid triangulation but I include it anyway.

```julia
julia> points = DelaunayTriangulation.get_lattice_points(0, 1, 0, 1, 25, 25, LinearIndices((1:25, 1:25))); # not public, fyi

julia> @benchmark triangulate($points; predicates = $AdaptiveKernel(), randomise = $false) samples = 1000
BenchmarkTools.Trial: 431 samples with 1 evaluation.
 Range (min … max): 9.882 ms … 158.046 ms ┊ GC (min … max): 0.00% … 92.85%
 Time (median): 10.969 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 11.596 ms ± 7.199 ms ┊ GC (mean ± σ): 3.74% ± 6.06%

  ▁ ▄██▆▅▅▆▃▂▁
  █▇▇██████████▇▄▅▃▃▃▂▃▁▂▃▁▃▂▁▃▁▁▂▁▃▁▂▂▂▂▁▁▂▂▂▁▂▁▁▁▃▁▂▁▁▁▁▂▁▁▂ ▃
  9.88 ms Histogram: frequency by time 18.3 ms <

 Memory estimate: 2.92 MiB, allocs estimate: 8295.

julia> @benchmark triangulate($points; predicates = $ExactKernel(), randomise = $false) samples = 1000
BenchmarkTools.Trial: 238 samples with 1 evaluation.
 Range (min … max): 14.463 ms … 209.383 ms ┊ GC (min … max): 0.00% … 56.42%
 Time (median): 16.461 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 21.007 ms ± 17.397 ms ┊ GC (mean ± σ): 11.87% ± 12.37%

  ▅█▆▄▃
  █████▇▅▇▇█▅▁▁▄▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▄▁▄▅▁▅▆▁▆▁▁▄ ▅
  14.5 ms Histogram: log(frequency) by time 72.1 ms <

 Memory estimate: 8.18 MiB, allocs estimate: 187394.

julia> @benchmark triangulate($points; predicates = $FastKernel(), randomise = $false) samples = 1000
BenchmarkTools.Trial: 332 samples with 1 evaluation.
 Range (min … max): 9.369 ms … 207.123 ms ┊ GC (min … max): 0.00% … 88.74%
 Time (median): 15.539 ms ┊ GC (median): 0.00%
 Time (mean ± σ): 15.080 ms ± 11.215 ms ┊ GC (mean ± σ): 4.28% ± 5.91%

    ▁▆▅▇█▃▁ ▂▅▄▁▁ ▁▁
  ▄▆███████▆▅▄▄▃▄▃▁▃▃▃▁▃▃▅▆█████▆▇▇▅██▆▃▆▄▃▁▃▄▃▃▄▃▃▁▃▃▁▁▃▁▁▁▃▃ ▄
  9.37 ms Histogram: frequency by time 24.8 ms <

 Memory estimate: 2.83 MiB, allocs estimate: 8306.

```

There are some other benchmarks I’ve done but, typically, `AdaptiveKernel()` being comparable to `FastKernel()` is expected and `ExactKernel()` lags a bit behind with many more allocations. When there are no issues like collinear points or cocircular points, all the kernels are about the same.

(Not all predicates when using `AdaptiveKernel()` use AdaptivePredicates.jl yet. `angle_is_acute` and `parallelorder` still use ExactPredicates.jl. See [Other predicates · Issue #18 · JuliaGeometry/AdaptivePredicates.jl · GitHub](https://github.com/JuliaGeometry/AdaptivePredicates.jl/issues/18))

---

<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:** [September 8, 2024, 8:32pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/11 "2024-09-08T20:32:42Z")

</div>

I’ve now released [DelaunayTriangulation.jl](https://github.com/JuliaGeometry/DelaunayTriangulation.jl) 1.3.0 which is a pretty big release, bringing with it three really nice new features:

1. Weighted Delaunay triangulations. These are triangulations of point sets where each point has an associated weight.
2. Power diagrams. These are dual to the weighted Delaunay triangulations. Here, the Voronoi cells are defined in terms of the power distance metric instead of the Euclidean distance, i.e. the metric \pi(p, q) = d(p, q)^2 - w\_p - w\_q, where d(p, q) is the Euclidean distance and w\_p and w\_q are the weights of p and q, respectively. This could be a nice way to add non-Euclidean metric support to NaturalNeighbours.jl if anyone was interested in that (note that calls to `triangle_circumcenter` would be replaced with appropriate calls to `triangle_orthocenter` when `is_weighted(tri)`, in addition to whatever else is needed.)
3. Clipped Voronoi tessellations to convex polygons other than just the convex hull or rectangles (still no support for non-convex boundaries). The limitation to convex polygons is because the Sutherland-Hodgman algorithm is used. Hopefully, in the future, I can eventually use the much better VoroCrust algorithm.

I show examples of these three features below. Please see the docs for more examples [Introduction · DelaunayTriangulation.jl](https://juliageometry.github.io/DelaunayTriangulation.jl/dev/).

 ![image](https://global.discourse-cdn.com/julialang/original/3X/b/a/ba1809b10525835f310bef38ae44f2c646ad2dbd.png)

```julia
using DelaunayTriangulation, CairoMakie, StableRNGs
using DelaunayTriangulation: EllipticalArc 
# Weighted triangulation 
rng = StableRNG(123)
points = rand(rng, 2, 50)
weights = randn(rng, 50)
tri1 = triangulate(points; weights, rng)

# Power diagram: Just pass a weighted triangulation to voronoi! 
vorn2 = voronoi(tri1; rng)

# Clipping to an ellipse 
points = 5randn(rng, 2, 100)
weights = rand(rng, 100)
tri3 = triangulate(points; rng, weights)
ellipse = EllipticalArc((2.0, 0.0), (2.0, 0.0), (0.0, 0.0), 2.0, 4.0, 0.0)
t = LinRange(0, 1, 200)
clip_points = ellipse.(t)
clip_vertices = [1:(length(clip_points)-1); 1]
clip_polygon = (clip_points, clip_vertices)
vorn3 = voronoi(tri3; rng, clip = true, clip_polygon)

fig = Figure()
ax1 = Axis(fig[1, 1], title = "Weighted", width = 300, height = 300)
ax2 = Axis(fig[1, 2], title = "Power", width = 300, height = 300)
ax3 = Axis(fig[1, 3], title = "Clipped", width = 300, height = 300)
triplot!(ax1, tri1)
voronoiplot!(ax2, vorn2, show_generators = false, clip = (-5, 5, -5, 5))
voronoiplot!(ax3, vorn3, show_generators = false)
resize_to_layout!(fig)
fig

```

---

<div class="post-metadata">

**Author:** ![Domenico\_Lahaye](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/domenico_lahaye/32/203728_2.png) [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)\
**Post date:** [September 9, 2024, 6:17pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/12 "2024-09-09T18:17:33Z")

</div>

Out of shear curiosity: can of above be used to generate meshes with boundary layer refinement to capture the use of wall function in Reynolds-averaged turbulent flow? Thx!

---

<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:** [September 9, 2024, 6:29pm UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/13 "2024-09-09T18:29:30Z")

</div>

I would probably need an example of what you need to be sure, but the `refine!` function allows you to pass a custom refinement function that could in principle allow you to refine more carefully around boundaries.

I have two examples of custom refinement:

> **[Mesh Refinement · DelaunayTriangulation.jl](https://juliageometry.github.io/DelaunayTriangulation.jl/stable/tutorials/refinement/#Constrained-triangulation-and-custom-constraints)**
>
> Documentation for DelaunayTriangulation.jl.

> **[Triangulating Curve-Bounded Domains · DelaunayTriangulation.jl](https://juliageometry.github.io/DelaunayTriangulation.jl/stable/tutorials/curve_bounded/#Using-Custom-Constraints-to-Control-Refinement)**
>
> Documentation for DelaunayTriangulation.jl.

Do those help? There are also tutorials that show you how to iterate properly over the boundaries if needed.

---

<div class="post-metadata">

**Author:** ![Domenico\_Lahaye](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/domenico_lahaye/32/203728_2.png) [@Domenico\_Lahaye](https://discourse.julialang.org/u/Domenico_Lahaye)\
**Post date:** [September 10, 2024, 5:40am UTC](https://discourse.julialang.org/t/ann-delaunaytriangulation-v1-0-curved-domains-and-improved-docs-code/113997/14 "2024-09-10T05:40:10Z")

</div>

Thanks for this info!