✳flâneur — a map of the web's best reading

Fast Polygon Triangulation Based on Seidel's Algorithm

gamma.cs.unc.edu · 1,046 words · saved by 1 readers

Atul Narkhede and Dinesh Manocha Department of Computer Science, University of North Carolina at Chapel Hill Click here to get the C source. Computing the triangulation of a polygon is a fundamental algorithm in computational geometry. In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries, as are described by splines [Kumar and Manocha 1994]. Methods of triangulation include greedy algorithms [O'Rourke 1994], convex hull differences [Tor and Middleditch 1984] and horizontal decompositions [Seidel 1991]. This Gem describes an implementation based on Seidel's algorithm (op. cit.) for triangulating simple polygons having no holes (The code has since then been extended to handle holes). It is an incremental randomized algorithm whose expected complexity is O(n log*n). In practice, it is almost linear time for a simple polygon having n vertices. The triangulation does not introduce any additional vertices and decomposes the polygon into n-

Fast Polygon Triangulation Based on Seidel's Algorithm Fast Polygon Triangulation Based on Seidel's Algorithm Atul Narkhede and Dinesh Manocha Department of Computer Science, University of North Carolina at Chapel Hill Getting the code Click here to get the C source. Introduction Computing the triangulation of a polygon is a fundamental algorithm in computational geometry. In computer graphics, polygon triangulation algorithms are widely used for tessellating curved geometries, as are described by splines [Kumar and Manocha 1994] . Methods of triangulation include greedy algorithms [O'Rourke 1

Explore this link on the map →

related reading