Stony Brook Algorithm Repository


Triangulation

Input
Output

Input Description: A set of points, or a polyhedron
Problem: Partition the interior of the point set or polyhedron into triangles.

Excerpt from The Algorithm Design Manual: Triangulation is a fundamental problem in computational geometry, because the first step in working with complicated geometric objects is to break them into simple geometric objects. The simplest geometric objects are triangles in two dimensions, and tetrahedra in three. Classical applications of triangulation include finite element analysis and computer graphics.

A particularly interesting application of triangulation is surface or function interpolation. Suppose that we have sampled the height of a mountain at a certain number of points. How can we estimate the height at any point \(q\) in the plane? If we project the points on the plane, and then triangulate them, the triangulation completely partitions the plane into regions. We can estimate the height of \(q\) by interpolating among the three points of the triangle that contains it. Further, this triangulation and the associated height values define a surface of the mountain suitable for graphics rendering.


Implementations

triangle (rating 9)
Triangle (rating 9)
Fortune's 2D Voronoi diagram code (rating 8)
earcut (rating 7)
triangles (rating 7)
delaunay (rating 7)
delaunator (rating 7)
GTS-GNU Triangulated Surface Library (rating 7)
QMG (rating 7)
GEOMPACK (rating 5)
QHull (rating 5)


Recommended Books

Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf Computational Geometry in C by Joseph O'Rourke Computational Geometry by F. Preparata and M. Shamos

Related Problems


Polygon Partitioning

Voronoi Diagrams

Go To Main Page