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

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, GraphicsMeshFindIntersections[]

• 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?

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

• Thanks for your explanation about DiscretizeGraphics[], DiscretizeGraphics[]. I know the boundary coordinates could be achieved via built-in RegionBoundary[], is it possible to know its thorry? – xyz Apr 21 '16 at 7:43
• I suppose you mean for the symbolic case? There, I believe, it constructs CAD cells, but I am not sure. For the numeric case, the boundary is sampled, this was developed in house so I don't think there are papers. – user21 Apr 21 '16 at 9:04
• No, @user21 I don't care about the symbolic case, rather than the numerical case. Anyway, thanks a bunch! – xyz Apr 21 '16 at 9:22

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