The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.3 Triangulation

Problem Input | Problem Output

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: A Two-Dimensional Quality Mesh Generator (C) (rating 9)
  • Fortune's 2D Voronoi diagram code (C) (rating 8)
  • GTS-GNU Triangulated Surface Library (C) (rating 7)
  • QMG: mesh generation and related software (C++) (rating 7)
  • GEOMPACK - triangulation and convex decomposition code (FORTRAN) (rating 5)
  • Qhull - higher dimensional convex hull program (C) (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



    This page last modified on 2008-07-10 .
    www.algorist.com