Thumbnail Image

Modification of Fournier and Montuno's Triangulation Algorithm for Simple Polygons�

Adi, Soehadi
Triangulation of a simple polygon is an important part of the application of geometry problems in computer graphics. A conventional triangulation algorithm runs in O(n2). Faster tringulation methods have been developed but these methods are more complicated. A simpler triangulation method was developed by Fournier and Montuno, which runs in O(n log n). The modified triangulation algorithm presented here compares favorably with the Fournier and Montuno's triangulation algorithm and is simpler in the sense of elimination of recursion. The Fournier and Montuno's triangulation algorithm and the modified triangulation algorithm are implemented using c. The performance of the two algorithms is analyzed using various data.