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.

The best books available for this problem are Computational Geometry in C by Joseph O'Rourke and Computational Geometry : Algorithms and Applications by Mark De Berg, Marc Van Kreveld, Mark Overmars, and O. Schwartskopf.


Implementations

  • Triangle: A Two-Dimensional Quality Mesh Generator (C) (rating 9)
  • GTS-GNU Triangulated Surface Library (C) (rating 9)
  • GEOMPACK - triangulation and convex decomposition code (FORTRAN) (rating 8)
  • Fortune's 2D Voronoi diagram code (C) (rating 7)
  • Qhull - higher dimensional convex hull program (C) (rating 6)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 6)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)
  • GraphEd -- Graph Editor and Layout Program (C) (rating 4)
  • 3D Convex Hull algorithm in Java (C) (rating 3)

    Related Problems

  • Polygon Partitioning
  • Voronoi Diagrams


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .