This project investigates the use of triangulations (TINs) to represent and compute
on very large terrains in GIS. While rasters are very popular and widely available
and supported, both in theory and in practice, TINs are not as well represented in
GIS packages, and in particular in GRASS. However, because the resolution of TINs is
not fixed, but adapts to the terrain, TINs have the potential of being more (space)
efficient than rasters, especially for very large terrains.
We study the problem of finding a scalable approach for simplifying a raster into a
TIN that approximates it within a specified error threshold. By scalable here we mean
that the algorithm should work well as the size of the input raster becomes very
large, exceeding the amount of main memory available on the machine. Our module,
r.refine, is implemented in GRASS for use and experimentation by the GRASS community.
The approach can be extended to simplifying arbitrary point-data and thus could be
useful for processing LIDAR data.
We present experimental results of r.refine showing that TINs of desired accuracy can
be obtained efficiently from (very large) rasters; and, despite all the overhead of
storing the topology, TINs are much more space-efficient than rasters of comparable
accuracy. For example, for error thresholds of 0.01%, a grid of xxx MB can be
represented as a TIN of xxx MB, which is a xxx reduction in size. Thus a raster of
xxGB can be represented as a TIN of XXMB. This space reduction of TINs is a reason to
believe that terrain analysis modules that operate on TINs would be much faster than
their counterparts on rasters.