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.
Type de document :
Article dans une revue
Computer Graphics Forum, Wiley, 1994, Eurographics, 13 (3), pp.281-292. 〈http://onlinelibrary.wiley.com/doi/10.1111/1467-8659.1330281/abstract〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00545173
Contributeur : Rémi Ronfard <>
Soumis le : jeudi 11 septembre 2014 - 12:18:39
Dernière modification le : mercredi 11 avril 2018 - 01:59:24

Identifiants

  • HAL Id : inria-00545173, version 1

Collections

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. 〈http://onlinelibrary.wiley.com/doi/10.1111/1467-8659.1330281/abstract〉. 〈inria-00545173〉

Partager

Métriques

Consultations de la notice

151