A Linear Time Algorithm for Triangulating a Point-Visible Polygon
Tony C. Woo, Sung Yong Shin · Cumulative Index of Computer Aided Architectural Design · 1985
The triangulation of a point-visible (star-shaped) polygon cannot be performed trivially if its kernel does not share a vertex with the polygon. The paper presents a triangulation algorithm that exploits point-and strong edge-visibility. It is through these two properties that the authors are able to triangulate in linear time. After classifying simple polygons by visibility, the authors show that strongly edge-visible polygons can be triangulated in linear time. A point-visible polygon is transformed into a strongly edge-visible polygon by the following steps: partitioning with a ray, partially triangulating both partitions, merging the two remaining polygons, and showing that the merged polygon is a strongly edge-visible polygon