have been known for a while. See for instance Lee and Schachter [74], Guibas
and Stolfi [59], or any textbook on computational geometry [18, 91, 98].
When the interpolation provided by the Delaunay triangulation is not appro-
priate, one can use different, more advanced interpolation methods like natural
neighbor interpolation [54, 99, 106], weighted moving averages [4], splines [40],
or Kriging [4, 123]. It is possible to combine the advantages of the TIN with the
quality of these more advanced interpolation methods as follows. Suppose we are
given the point set P together with an interpolation function and a maximum
error. The idea is: construct a TIN based on P and the interpolation function,
such that at any point, the interpolated elevation and the elevation given by the
TIN differ by at most the maximum error. Now it may not suffice to use only
the points of P as TIN vertices, and we need to select more points. Ideally, we
select as few points as possible, the optimization problem that shows up is very
difficult. Heuristics can be used to choose additional points as vertices in the
TIN, and hopefully not too many additional ones. It may also be the case that
only a subset of the points of P is needed to represent the interpolation function
with the desired accuracy. Or perhaps a completely different set of points is best.
In any case, finding a TIN with minimum number of vertices will be difficult.
It is known that the problem of computing a TIN with the minimum number
of vertices, given a TIN and a maximum allowed error, is an NP-hard problem,
implying that efficient algorithms are unlikely to exist.
4.2 From Grid to TIN
Grid-to-TIN conversion can be seen as a special case of the conversion of sample
points to a TIN. Also, grid-to-TIN conversion can be seen as a special case
of TIN generalization: reducing the number of vertices of a TIN to represent
a terrain. A grid can simply be triangulated to a fine regular triangulation.
Various algorithms have been proposed in the literature; see for instance the
survey by Garland and Heckbert [49], see also Lee [78]. Most of the methods
have the following distinguishing features: (1) selecting which grid points to
keep or discard, and (2) deciding when to stop selecting or discarding.
One method decides which grid points to keep or discard by initially assigning
an importance to each grid point [8]. The importance is determined by comparing
the elevation of a grid point with the interpolated elevation at the grid point
based oll the elevations of the eight neighbors. Only the grid points where the
difference is greatest are kept. These points can be triangulated, for instance
using the Delaunay triangulation, and become the TIN vertices.
A second method differs from the previous one by discarding grid points
incrementally instead of using a precomputed importance [77, 78]. In a sense,
the importance computation is postponed until the point is really discarded. A
more detailed description follows later.
Thirdly, there are methods that start out with a coarse triangulation of only
the four corner grid prints, and keep on refining the triangulation by adding
more points in the triangles [34~ 49, 61, 108]. Refining a triangle further stops
when the triangle approximates the grid points that lie in it sufficiently well.
47