6
$\begingroup$

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

enter image description here

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?
$\endgroup$

2 Answers 2

11
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – xyz
    Apr 21, 2016 at 7:43
  • $\begingroup$ 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. $\endgroup$
    – user21
    Apr 21, 2016 at 9:04
  • $\begingroup$ No, @user21 I don't care about the symbolic case, rather than the numerical case. Anyway, thanks a bunch! $\endgroup$
    – xyz
    Apr 21, 2016 at 9:22
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.