Click here to get the C source.

Computing the triangulation of a polygon is a fundamental algorithm in computational geometry. In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries, as are described by splines [Kumar and Manocha 1994]. Methods of triangulation include greedy algorithms [O'Rourke 1994], convex hull differences [Tor and Middleditch 1984] and horizontal decompositions [Seidel 1991].

This Gem describes an implementation based on Seidel's algorithm
(*op. cit.*) for triangulating simple polygons having no holes
** (The code has since then been extended to handle holes)**.
It is an incremental randomized algorithm whose expected complexity is

Generating monotone polygons from the trapezoid formation

The algorithm proceeds in three steps as shown in Figure 1.

All the data-structures used in the implementation are
statically allocated. The trapezoid formation requires a structure where
the neighbors of each trapezoid and its neighboring segments can be
determined in constant time. Therefore, for every trapezoid, the indices
of its neighbors and the segments are stored in its table-entry **T**.

The query-structure **Q**, used to determine the location of a point, is
implemented as described by Seidel. The same **Q** can be later used for fast
point-location queries. Both **Q** and **T** are updated as a new segment is
added into the existing trapezoid formation. This entails splitting in two the
trapezoid(s) in which the endpoints of the segment lie, then traversing along
the edge of the segment to merge in any neighboring trapezoids which both share
the same left and right edges and also share a horizontal edge.
All the monotone polygons are stored in a single linked list with pointers to
the first vertex in the list stored in a table.

Table 1 shows the average running time of the algorithm for randomly generated data sets of various sizes. All the measurements were taken on an HP Series 735 with execution times averaged over one hundred repetitions.

Empirical testing has proven the method robust across wide class of input data. The present implementation uses an epsilon tolerance when testing for floating-point equality. This computation occurs when determining whether a point lies to the left (right) of a segment or when detecting coincident points. This tolerance could potentially be removed by substituting a well-crafted point-in-polygon test [Haines 1994].

The triangulation code is invoked through the main interface routine,

with anint triangulate_polygon(n, vertices, triangles);

additional details appear in the C source code which accompanies this Gem.int is_point_inside_polygon(vertex);

**Bloomenthal 1994**-
Jules Bloomenthal.
An implicit surface polygonizer.
In Paul Heckbert, editor,
*Graphics Gems IV*, pages 324-349. Academic Press, Boston, 1994. **Fournier and Montuno 1984**-
A. Fournier and D.Y. Montuno.
Triangulating simple polygons and equivalent problems.
*ACM Trans. on Graphics*, 3:153-174, 1984. **Haines 1994**-
Eric Haines.
Point in polygon strategies.
In Paul Heckbert, editor,
*Graphics Gems IV*, pages 24-46. Academic Press, Boston, 1994. **Kumar and Manocha 1994**-
S. Kumar and D. Manocha.
Interactive display of large scale NURBS models.
Technical Report TR94-008, Department of Computer Science,
University of North Carolina, 1994.
**Lischinski 1994**-
Dani Lischinski.
Incremental Delaunay triangulation.
In Paul Heckbert, editor,
*Graphics Gems IV*, pages 47-59. Academic Press, Boston, 1994. **O'Rourke 1994**-
J. O'Rourke.
*Computational geometry in C*. Cambridge University Press, 1994. **Seidel 1991**-
R. Seidel.
A simple and fast incremental randomized algorithm for computing
trapezoidal decompositions and for triangulating polygons.
*Computational Geometry: Theory and Applications*, 1(1):51-64, 1991. **Tor and Middleditch 1984**-
S. B. Tor and A. E. Middleditch.
Convex decomposition of simple polygons.
*ACM Trans. on Graphics*, 3(4):244-265, 1984. **Narkhede and Manocha 1995**-
A. Narkhede and D. Manocha.
*Graphics Gems 5*, Editor: Alan Paeth, Academic Press, 1995.

This document was generated using the **LaTeX**2`HTML`
translator Version 0.5.3 (Wed Jan 26 1994) Copyright © 1993, Nikos Drakos,
Computer Based Learning Unit, University of Leeds.

narkhede@cs.unc.edu

hits since November 1995.