Topologically sweeping the visibility complex of polygonal scenes
Résumé
In order to do efficient visibility computations in the plane, one must deal with maximal free line segments, that is line segments of maximal length in free space. To that end, [PV93b] introduce, for scene of convex curved objects, a new data structure, the visibility comp~ex, whose elements represent classes of maximal free segments having the same visibilities. In particular the visibility complex contains the visibility graph. We have studied the visibility complex for general polygonal scenes, and have devised an algorithm for topologically sweeping the visibility complex (and so for computing the visibility graph with the same complexity) in optimal time O(n log n + m) and optimal space O(n), where n is the total number of polygon vertices, and m the size of the visibility graph. Since it is a sweep algorithm, it improves the space storage of [GM87] for computing the visibility graph of polygonal scenes. Moreover, we have implemented our algorithm and we have made experimental comparisons with two other sweep algorithms for computing visibility graphs : the algorithm of [OW88] and the algorithm of [PV93a], which both run in time O(m log n). They were tested on scenes composed of line segments. We see that the gain due to the suppression of the logarithmic cost is significant.