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 - Graphisme, Vision et Robotique, 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 metadatas

https://hal.inria.fr/inria-00545173
Contributor : Rémi Ronfard <>
Submitted on : Thursday, September 11, 2014 - 12:18:39 PM
Last modification on : Wednesday, April 11, 2018 - 1:59:24 AM

Identifiers

  • HAL Id : inria-00545173, version 1

Collections

IMAG | CNRS | INRIA | UGA

Citation

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

Share

Metrics

Record views

224