| 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 13:58 |
|
