Remarks on the computation of the horizon of a digital terrain

摘要

The problem of determining the horizon of a terrain viewed from a given point is addressed. A triangulated surface model of the terrain is often used to this aim, because such a model is simple and flexible. In all contributions where the problem is explicitly discussed, it is assumed that the horizon can be determined by computing the upper envelope of a set of segments in the plane. This conjecture is shown here to be wrong. One of the major consequences of this error concerns the determination of the visible portion of a terrain. Indeed, the algorithms available for this purpose process the terrain triangles in distance order from the viewpoint and are based on the updating of the horizon associated with the already visited triangles, that can cast shadow on the not yet visited ones. The consequence of a wrong computation of the horizon is that some invisible portions of the terrain can be classified as visible. Moreover, the extension of the wrongly classified area depends upon the configuration of the terrain and can be arbitrarily large even for an arbitrarily small error in horizon computation.