Region intervisibility in terrains
A polyhedral terrain is the graph of a continuous piecewise linear function defined over the triangles of a triangulation in the xy-plane. Two points on or above a terrain are visible to each other if the line-of-sight does not intersect the space below the terrain. In this paper, we look at three related visibility problems in terrains. Suppose we are given a terrain T with n triangles and two regions R-1 and R-2 on T, i.e., two simply connected subsets of at most m triangles. First, we present an algorithm that determines, for any constant is an element of > 0, within O(n(1+is an element of)m) time and storage whether or not R-1 and R-2 are completely intervisible. We also give on O(m(3)n(4)) time algorithm to determine whether every point in R-1 sees at least one point in R-2. Finally, we present an O(m(2)n(2)log n) time algorithm to determine whether there exists a pair of points p is an element of R-1 and q is an element of R-2, such that p and q see each other.
polyhedral terrains visibility