Triangulation section

[DanielVandH]

Another section that could be added is about Triangulations/Tessellations. There are several packages ( too many :) ):

DelaunayTriangulation.jl (native); VoronoiDelaunay.jl (native); VoronoiCells.jl (native); Delaunay.jl (wrapper); MiniQhull.jl (wrapper); DirectQhull.jl (wrapper); Delaunator.jl (native); TriangleMesh.jl (wrapper); Triangulate.jl (wrapper); Triangle.jl (wrapper); TetGen.jl (wrapper - 3D)

[KronosTheLate]

That is a great list. I had no idea that there were so many! I am starting to think that some domains need a hidden section on minor packages that can be folded out, as the sheer number of packages might overwhelm users looking to make a choice 😅

Do you have any experience in using them? Would you be able to write about what they are good/bad at, and how they relate to each other? If yes, keep in mind that the goal is to help user make an informed choice about the most appropriate package for their use case, whatever that might be.

[DanielVandH]

It is indeed quite long. Why are there three wrappers for the same library :).

Here is a list of what they do (disclaimer: I wrote DelaunayTriangulation.jl, this list is from https://github.com/DanielVandH/DelaunayTriangulation.jl#similar-packages, except that I've added DelaunayTriangulation.jl into the list):

• DelaunayTriangulation.jl: A pure Julia library for constructing planar triangulations with support for both unconstrained and constrained triangulations (including domains with holes, disjoint domains, etc.), mesh refinement, Voronoi tessellations, clipped and centroidal Voronoi tessellations, and dynamic updates. Uses exact geometric predicates and supports custom types.
• VoronoiDelaunay.jl: A pure Julia library that constructs planar triangulations and tessellations, 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.

My package is the one that's the most fleshed out at this point, and the only one with easy support for mesh refinement/constrained triangulations (except maybe Triangle.jl I think, but that's a wrapper). I also don't think many of these are even maintained anymore - the last commit dates are:

• TetGen.jl: Jun 2, 2022 (462 days)
• TriangleMesh.jl: May 27, 2021 (833 days)
• Triangulate.jl: Oct 10, 2022 (322 days)
• Triangle.jl: Jul 22, 2022 (412 days)
• Delaunator.jl: May 50, 2023 (125 days)
• DirectQhull.jl: Mar 10, 2023 (181 days)
• MiniQhull.jl: Sep 29, 2022 (343 days)
• Delaunay.jl: May 12, 2022 (483 days)
• VoronoiCells.jl: Apr 12, 2023 (148 days)
• VoronoiDelaunay.jl: Jun 28, 2023 (71 days - and this commit was to add a note that the package is only in maintenance mode)
• DelaunayTriangulation.jl: Today

[DanielVandH]

In terms of a short summary, the advice I would give is: DelaunayTriangulation.jl is the most supported package for Delaunay triangulations in two dimensions, although I believe Delaunator.jl might be faster for unconstrained triangulations if you do not need exact arithmetic (but I don't think you should ever want to skip exact arithmetic - I've not done the performance comparison myself. Delaunator.jl also only does unconstrained triangulations, no constraints allowed). In higher dimensions, you need Delaunay.jl if $n > 3$, or TetGen.jl is great if $n=3$.

[joa-quim]

You may add also GMT.jl to the list.

• Shewchuk triangulation
• Spherical triangulation

[DanielVandH]

Must've missed those in my searching, sorry about that @joa-quim. Looking at the docs, am I right that it allows for both 2D and 3D unconstrained triangulations / Voronoi tessellations? Does it support mesh refinement / constrained triangulations? Here's a draft item:

• GMT.jl: A wrapper of GMT, allowing for unconstrained Delaunay triangulations in two- or three-dimensions, and for spherical triangulation, i.e. triangulation of points lying on a sphere.

Anything else you would like mentioned there? I'll also add it to my list on DelaunayTriangulation.jl - the spherical triangulation is a very nice feature.

[joa-quim]

Yep, GMT is a big hat and people often miss many of its contents 😄

Does it support mesh refinement / constrained triangulations?

No, and it's only 2D. But the triangulate module let also compute regular grids from the Delaunay triangulation.

[DanielVandH]

Oh, so

Reads x,y[,z] from file or table and performs Delaunay triangulation

just means that the z data is used as if it were function data? That might be worth clarifying in those docs (unless I just can't read in the morning :) ). I will also add this now to DelaunayTriangulation.jl's list also - thanks.

[joa-quim]

Yes, z is optional. It is used as z = f(x,y) when the triangulate module is used to compute grids or used to make contour plots of scatter after triangulate them.

I'll try to clarify that tomorrow (I seem to be on the other side of the world. One o'clock here).

Some of the examples at https://www.generic-mapping-tools.org/GMTjl_doc/examples/contours/01_contour_examples/#example_1192055388678784833 show usage for contouring.

[KronosTheLate]

Fantastic. You are both clearly much more fit to write about this. PR's are most welcome. I will probably get around to it in a few days (semester starting now).

If I beat you to it, I will likely just copy your excellent take on it. The bullet list and summarizing recommendation are exactly the type of content I have in mind. I would just change the wording and structure slightly to fit better in a public resource ^_^

Thanks for the detailed comments <3

[joa-quim]

That might be worth clarifying in those docs

Added this paragraph to triangulate docs

Using `x,y[,z]` or only `x,y` in input depends on the intended usage of this module. If only the
triangulation is desired, then only `x,y` is used and even if the input table has a `z` column,
that is ignored. If, however, we wish to compute a grid (see below) than `z` is mandatory and
is interpreted as a functional value, ``z = f(x,y)``.

[KronosTheLate]

I will add the following entry to the readme. Please open up a PR if you have corrections, or @ me here if there is something that needs further discussion.

Triangulations/Tessellations

In modeling, it is often neccesary to discretize space. This is often referred to as "triangulation" or "tessellation". This section is dedicated to packages that provide such functionality.

Short summary

DelaunayTriangulation.jl is the most supported package for Delaunay triangulations in two dimensions. Delaunator.jl might be faster for unconstrained triangulations if you do not need exact arithmetic, and if you do not need constrained tesselations. In higher dimensions, you need Delaunay.jl if $n > 3$, or TetGen.jl is great if $n=3$.

List of packages with short descriptions

• DelaunayTriangulation.jl: A pure Julia library for constructing planar triangulations with support for both unconstrained and constrained triangulations (including domains with holes, disjoint domains, etc.), mesh refinement, Voronoi tessellations, clipped and centroidal Voronoi tessellations, and dynamic updates. Uses exact geometric predicates and supports custom types.
• VoronoiDelaunay.jl: A pure Julia library that constructs planar triangulations and tessellations, 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.
• GMT.jl: A wrapper of GMT, allowing for unconstrained Delaunay triangulations in two dimensions, and for spherical triangulation, i.e. triangulation of points lying on a sphere.

Note that many of these are likely not maintained anymore - the last commit dates are, going from more to less recent:

• DelaunayTriangulation.jl: Sep 13, 2023
• VoronoiDelaunay.jl: Jun 28, 2023 (This commit was to add a note that the package is only in maintenance mode)
• Delaunator.jl: May 50, 2023
• VoronoiCells.jl: Apr 12, 2023
• DirectQhull.jl: Mar 10, 2023
• Triangulate.jl: Oct 10, 2022
• MiniQhull.jl: Sep 29, 2022
• Triangle.jl: Jul 22, 2022
• TetGen.jl: Jun 2, 2022
• Delaunay.jl: May 12, 2022
• TriangleMesh.jl: May 27, 2021