A linear-time algorithm for solving the strong hidden-line problem in a simple polygon |
| |
Authors: | Godfried T. Toussaint |
| |
Affiliation: | McGill University, School of Computer Science, Montreal H3A 2K6, Quebec, Canada |
| |
Abstract: | A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P. |
| |
Keywords: | Weak visibility strong hidden-line problem triangulation computer graphics computer geometry shortest paths |
本文献已被 ScienceDirect 等数据库收录! |
|