CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

authors Woo, Tony C. and Shin, S. Y.
year 1985
title A Linear Time Algorithm for Triangulating a Point-Visible Polygon
source ACM Transactions on Graphics. January, 1985. Vol. 4: pp. 60-70 : ill. includes bibliography
summary 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
keywords algorithms, polygons, triangulation, computational geometry
series CADline
references Content-type: text/plain
last changed 2003/06/02 11:58
HOMELOGIN (you are user _anon_352589 from group guest) Works Powered by SciX Open Publishing Services 1.002