Horizon Computation
Similar approaches as those illustrated in the previous section
can be used to compute other visibility structures
on a terrain, for instance, the horizon.
The horizon of a terrain [Cole and Sharir 1989]
corresponds to the distal boundary of the visible area
from a viewpoint in all directions.
More formally, the horizon is the locus of points
P, lying on the terrain surface, such that:
- P is visible from V, and
- for any point Q on the surface, such that
such that the projections of P, Q, and V onto the xy-plane
are aligned, with the one of P lying between the other two,
Q is not visible from V.
On a TIN, the horizon is a chain of portions of
triangle edges, radially sorted around the viewpoint.
A worst-case size of
Θ(nα(n)) has been
proven for the horizon of a TIN with n vertices [].
Algorithms for computing the horizon of a viewpoint of a TIN
have been proposed in [,,].
Similar error thresholds as those introduced in Section
![[*]](/file/20193/2015-02-11.ftp.disi.unige.it.tar/ftp.disi.unige.it/pub/.person/PuppoE/VARIANT/variant.tex/crossref.png)
can be used for extracting a TIN from an MT;
existing horizon algorithms are then applied to such TIN.
As in the case of viewsheds, a dynamic approach can be
used to interactively refining an initially sketched the horizon.
Dynamic horizon algorithms can be used for such a purpose.
As in Section , we assume that the sizes of
the current and of the previous TIN are both in Θ(n)
and we denote by kold and knew the number of triangle
removed and inserted, respectively, when passing from the previous
to the current TIN.
The horizon can be either re-computed from scratch,
or dynamically updated.
In the following, we compare these two approaches.
Re-computing the horizon by scratch costs
O(n log n),
if the optimal algorithm by Hershberger [] is used.
The update of the horizon costs
O((kold + knew)α(n)log n).
The update process is convenient when
kold and
knew = O(
)
(note that α is very close to be a constant function of n).