Triangulating multiply-connected polygons: A simple yet efficient algorithm

International audienceWe 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