Consider a viewpoint moving amongst a set of non-intersecting line segments in the plane. We would like to compute efficiently the set of segments visible at successive positions along the viewpoint trajectory. This problem can be solved in either the off-line or the on-line setting. The latter case, in which the updates of the viewpoint are known only as they occur, is more interesting for interactive systems.
This video illustrates a simple algorithm to solve this problem. For a scene containing m visual discontinuities, each discontinuity crossing is performed in time O(log^2 m) using space O(m). The space bound is an important consideration, as m can become very large in real applications.
23 Kb compressed Postscript file
@inproceedings{GS-cg96,
author = "Sherif Ghali and A. James Stewart",
title = "Maintenance of the Set of Segments Visible from a Moving Viewpoint
in Two Dimensions",
booktitle = "Proceedings of the 12th Annual ACM Symposium on Computational Geometry",
year = "1996",
month = "May",
pages = "V3--V4"
}