Overview

This section gives some mathematical details for the algorithms in this package. Not all details of the algorithms will be provided in these discussions, only those sufficient for understanding the algorithms themselves. We only discuss a specific set of algorithms in this package where extra mathematical details could be useful. For example, we do not give a section on point location since there the math is reasonably straightforward, as described in the triangulation section, and the main complexity is just on getting a working implementation. We do not talk about e.g. how we manually compute convex hulls without a triangulation since they are not a main focus in any part of this package (even though we do provide a function for it). Our discussion in these sections follows several references:

• The book Delaunay Mesh Generation by Cheng, Dey, and Shewchuk (2012). This is a great book that discusses in detail the algorithms for Delaunay triangulations and mesh generation.
• The book Computational Geometry: Algorithms and Applications by de Berg, Cheong, Kreveld, and Overmars (2008, 3d). This book is a great reference for computational geometry in general.
• The PhD thesis Delaunay Refinement Mesh Generation of Curve-bounded Domains by Serge Gosselin (2009). This thesis discusses the algorithms for mesh refinement in detail, and is the basis of our implementation of mesh refinement for curve-bounded domains. Another good reference for this topic is the PhD thesis Delaunay refinement for curved complexes by Adriano Lisboa (2008).
• The paper Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator by Shewchuk (2005) is a great paper discussing constrained Delaunay refinement. Similarly, Shewchuk's PhD thesis (1997) is a great reference.
• Shewchuk's paper Adaptive precision floating-point arithmetic and fast robust geometric predicates is a good reference regarding the necessity of, and construction of, fast robust geometric predicates, as well as his lecture notes.
• The paper Fast segment insertion and incremental construction of constrained Delaunay triangulations by Shewchuk and Brown (2015) is where our implementation of constrained Delaunay triangulations comes from.
• The resource A Primer on Bézier Curves by Pomax is a great resource for understanding Bézier curves and their properties. Similarly, The NURBs Book by Piegl and Tiller (1997) is a great reference for implementing BSplines.
• The website https://www.mvps.org/directx/articles/catmull/ by Robert Dunlop (last updated 2005) was useful for understanding Catmull Rom splines, as well as https://qroph.github.io/2018/07/30/smooth-paths-using-catmull-rom-splines.html by Mika Rananen (2018). Lastly, the notes by Christopher Twigg, https://www.cs.cmu.edu/~fp/courses/graphics/asst5/catmullRom.pdf, were helpful.
• The paper Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations by Mücke, Saias, and Zhu (1999) is where our point location algorithm comes from.
• The paper Where and how Chew's second Delaunay refinement algorithm works by Rand (2011) discusses Chew's algorithm for mesh refinement, originally introduced by Shew in 1993 in _Guaranteed-quality mesh generation for curved surfaces.
• The paper Delaunay refinement by corner lopping is another good reference for mesh refinement on curved domains.
• The paper Guaranteed-quality triangular mesh generation for domains with curved boundaries was our initial reference for triangulating curved-bounded domains, although now we only source it for ideas on implementing curves generically.
• The resource https://www.bartoszsypytkowski.com/r-tree/ by Bartosz Sypytkowski was useful for understanding and properly implementing R-Trees, as was the code in SpatialIndexing.jl.
• The paper Efficient computation of clipped Voronoi diagram for mesh generation by Yan, Wang, Lévy, and Liu (2013) is a good reference for clipped Voronoi tessellations.
• The Wikipedia article for the Sutherland-Hodgman algorithm is a good resource for understanding and implementing it, as is the article for the Liang-Barsky algorithm.