Skip to Main content Skip to Navigation
New interface
Journal articles

Triangulating multiply-connected polygons: A simple yet efficient algorithm

Rémi Ronfard 1 J. Rossignac 2 
1 MOVI - Modeling, localization, recognition and interpretation in computer vision
GRAVIR - IMAG - Laboratoire d'informatique GRAphique, VIsion et Robotique de Grenoble, Inria Grenoble - Rhône-Alpes, CNRS - Centre National de la Recherche Scientifique : FR71
Abstract : We present a new, simple, yet efficient algorithm for triangulating multiply-connected polygons. The algorithm requires sorting only local concave minima (sags). The order in which triangles are created mimics a flooding process of the interior of the polygon. At each stage, the algorithm analyzes the positions and neighborhoods of two vertices only, and possibly checks for active sags, so as to determine which of five possible actions to take. Actions are based on a local decomposition of the polygon into monotonic regions, or gorges. The implementation is extremely simple and numerically robust for a large class of polygons. It has been tested on millions of cases as a pre-processing step of a walkthrough and inspection program for complex mechanical and architectural scenes. Extensive experimental results indicate that the observed complexity in terms of the number of vertices remains under O(N^3/2) in all cases.
Document type :
Journal articles
Complete list of metadata
Contributor : Rémi Ronfard Connect in order to contact the contributor
Submitted on : Thursday, September 11, 2014 - 12:18:39 PM
Last modification on : Saturday, November 19, 2022 - 3:59:04 AM


  • HAL Id : inria-00545173, version 1


Rémi Ronfard, J. Rossignac. Triangulating multiply-connected polygons: A simple yet efficient algorithm. Computer Graphics Forum, 1994, Eurographics, 13 (3), pp.281-292. ⟨inria-00545173⟩



Record views