Graphics Gems V (IBM Version)

VII.5

Fast Polygon Triangulation Based on Seidel’s Algorithm

Narkhede Atul and Dinesh Manocha [e-mail],     Department of Computer Science University of North Carolina Chapel Hill, North Carolina; Department of Computer Science University of North Carolina Chapel Hill, North Carolina. E-mail address: [e-mail]

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, such as those 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 ...