Parallelized ear clipping for the triangulation and constrained Delaunay triangulation of polygons
Günther Eder, Martin Held, Peter Palfrader · Computational Geometry · 2018
We present an experimental study of strategies for triangulating polygons in parallel on multi-core machines, including the parallel computation of constrained Delaunay triangulations. As usual, we call three consecutive vertices of a (planar) polygon an ear if the triangle that is spanned by them is completely inside the polygon. Extensive tests on thousands of sample polygons indicate that about 50% of vertices of most polygons form ears. This experimental result suggests that polygon-triangulation algorithms based on ear clipping might be well-suited for parallelization. We discuss three different approaches to parallelizing ear clipping, and we present a parallel edge-flipping algorithm for converting a triangulation into a constrained Delaunay triangulation. All algorithms were implemented as part of Held's FIST framework. We report on our experimental findings, which show that the most promising method achieves an average speedup of 2–3 on a quad-core processor. In any case, our new triangulation code is faster than the sequential triangulation codes Triangle (by Shewchuk) and FIST.