The theory/algorithm knowledge behind the built-in Discretize* and Boundary*

Question

The ComputationalGeometry package was built-in in V10 distribution.

In classical computational geometry field, the following questions were investigated.

• Convex hulls, ConvexHullMesh[]

• Line segment intersection, Graphics`Mesh`FindIntersections[]

• Point location, RegionMember[]

• Voronoi diagrams, VoronoiMesh[]

• Delaunay triangulations, DelaunayMesh[]

• Boolean operations(like union, difference and intersection), RegionUnion[], RegionDifference[], RegionIntersection[]

which means I can find the theory/algorithm in classical textbook of computational geometry like: "Computational Geometry, Algorithms and Applications".

In addtion, new version also owns other new functionality, like: Discretize*, Boundary*

• DiscretizeGraphics[]
• BoundaryDiscretizeGraphics[]
• DiscretizeRegion[]
• BoundaryDiscretizeRegion[]
• RegionBoundary[]

---

So I would like to know:

• Is it possible to know the theory/algorithm behind the above functions. Namely, which textbook involved the theory/algorithm knowledge?

Answer 1

DiscretizeRegion[] and ToElementMesh[] at their core use TriangleLink and TetGenLink to make the mesh. Have a look at the documentation for specifics about these packages. Both ship with source code. As far as literature goes. Have a look at "Delaunay Mesh Generation" by Jonathan Shewchuk (Author) et al.

Package homepage

• Triangle : A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator

• TetGen: A Quality Tetrahedral Mesh Generator and a 3D Delaunay Triangulator

Answer 2

I don't know what algorithms the built-in functions implement, but here are a few books that implement some of the algorithms you seek:

Computational Geometry: Algorithms and Applications

Computational Geometry in C

Discrete and Computational Geometry

Computational Geometry: An Introduction

Finally, there is this one that deals with shape analysis:

Mathematical Tools for Shape Analysis and Description