**--------------------------------------------------------------------------------**

- breaklines - (X, Y,constant Z) and (X, Y,continuous Z)
- clifflines - (X, Y,constant Z, constant Z) only
- normal strings, eg contours - (X, Y, constant Z)
- spot heights - (X, Y, Z)
- ordinary string/data node
- river string/data node
- ridge-line string/data node
- inaccurate location of nodes,
- inaccurate node flagging,
- inaccurate node height values.
- Interpolation based on a linear triangle facet. Although the interior triangle surface will be smooth, none of the derivatives along the triangle edges or at the vertices will be continuous.
- Interpolation using a smooth surface patch fitted to the triangle vertices and estimated derivatives in a manner to ensure both a continuous surface and at least continuous first order derivatives.

The area of coverage for data structuring is specified by the user. As the triangulation is unique it is not necessary to map the whole area at once, but it is perfectly possible to join areas seamlessly by allowing a minimum of one triangle of overlap. This is a very powerful feature of the system.

All data are converted to integer on input to enhance execution speed. The basic system operates at a resolution of 150000 units in the longest map axis direction; equivalent to a positional accuracy of 0.015 mm for a map 1 metre long. Choice of coverage is therefore not crucial, but if super high resolution is required the map can be divided into sections and each section structured separately, gridded using TRIGRID and then assembled using DTITILE.

TRIANG supports the following data types:

In addition TRIANG supports the following node flags:

The neighbour search procedure does not rely on contour integrity - gaps are allowed, as are spot heights and discontinuities of slope. Thus one can use partially digitised maps where the digitising has attempted to maintain a given density of information rather than represent every contour. The effect of variable contour interval is shown in Figure 2.1. The information content is much more evenly spaced in the bottom section of the Figure than in the top, and would result in a better (or at least more even) surface representation. This is an acceptable form of data input, and can speed contour acquisition using manual methods in areas of varying relief. Contour strings can be supplemented by data strings for cliffs, ridge, river and valley lines to provide slope discontinuities, always bearing in mind that all locations will have to be tagged with height values.

TRIANG offers a triangulation constraint option which forces the Delaunay triangulation to honour the connectivity of the original data strings, thus preventing triangles from "leaking" through contours and other strings, see Figure 2.2.

If edge matching to adjacent DTMs is required, TRIANG provides the option to include relevant post values from the adjacent DTI format DTM as edge control to the current triangulation.

Output from TRIANG is in the form of binary node and Thiessen neighbour files. These are used directly by TRIEDIT (editor) and TRIGRID (grid creation).

TRIEDIT may be used to insert extra nodes or strings of nodes into the existing network in such a manner that links along the strings will remain connected in the network irrespective of string point spacing. This is particularly important for highway engineering examples or other boundary limit situations where the spacing between the points may well lead to severe "breaking" of discontinuity lines if included in the original data structuring.

The process of data insertion in TRIEDIT assumes permanent connections between points in an input string. The resulting triangulation is a distortion of the Delaunay criterion, and hence any retriangulation of the data set including these unbreakable strings could lead to problems. The triangular structure modified in this manner can therefore only be used in TRIGRID and later phases.

TRIDER takes the binary triangulation node and neighbour files created by TRIANG (or edited output from TRIEDIT) and produces an output file containing slope derivatives at each data point in the triangulation. These data may then be used by TRIGRID in conjunction with the node and data files as the basis for DTM grid estimation. Once TRIDER has been used to generate a slope derivative file many subsequent runs of TRIGRID may be made to produce DTM grids at differing resolutions.

TRIDER is also used to provide Z values for the imaginary points generated around the edge of the triangulation by TRIANG. Four interpolation options are available for imaginary point estimation, the default is based on a trend surface fit through data points for which Z values are known. TRIDER must be re-run to produce a new derivative file every time the triangulation node and data files are modified.

Grids (DTMs) of virtually unlimited size can be created from the spatial structure created by TRIANG (or TRIEDIT) and TRIDER using TRIGRID. The program automatically chops the DTM into sections that hold as many rows of the DTM as possible for the amount of memory available. An example of the grid generation process is shown in Figure 2.3. In this example, three passes through the neighbour network are needed to complete the grid. The program will often contain the entire DTM at one pass. For larger DTMs the program will automatically make the appropriate number of passes through the data to ensure that the grid is complete.

The Thiessen node-neighbour file created by TRIANG supplies the structure from which the triangles are generated. These triangles are then mapped into the DTM (Figure 2.4) so that all grid nodes that fall within triangles are assigned values based on the values, and possibly the estimated derivatives, at the vertices of the triangles. Triangles can be dumped quickly into the DTM without need for point in polygon checks.

TRIGRID uses two methods of interpolating the height value for a grid node position within a given triangle area:

The linear facet approach results in a perfectly acceptable surface where the data density is high in relation to the grid being generated, or the surface gradient is low. In such cases the flat facet of any triangle will probably supply only one or two nodes of the final DTM, and will have a slope in close agreement with the actual surface.

Smooth surface interpolation requires considerable computation owing to the irregular triangle shapes but will be worthwhile where the surface is considered "smooth" - for instance where the DTM is intended to represent not terrain but some thematic variable such as gravity data isarithms. The requirements for many DTMs are, however, rather different. In the case of terrain the existence of varying morphology within the DTM area - plains, rolling hills, mountains, cliffs, lakes and sea shores - may make the use of a smooth curved patch function essential. The patch must be continuous but not necessarily all directions. For instance where a ridge or river line indicates a discontinuity that discontinuity must be reflected in the patch covering the triangle area. Other limitations may also apply. For instance where contour data has been used, and in all possible contours of a fixed height interval are present, the interpolation procedure must not give a value that is above the next contour height, or below the last one.

When using smooth patch interpolation an option is provided to apply automatic interpolation limits which take into account triangle facet slope and the feature codes of the triangle vertex points.

TRIGRID offers an option to trace along the original data strings upon which the triangulation is based. Up-hill/down-hill side of line information is collected for each string. This may be used to supplement or override the slope derivatives estimated for triangles which have all three vertices at the same height on the same string, eg a contour.

Estimation of the derivatives at each data point is an essential precursor to any smooth patch calculation. This process employs a separate pass through the Thiessen node-neighbour file to enable local distance weighted estimates of the partial derivatives to be calculated.

Figure 2.5 shows both the standard situation with continuity guaranteed across the triangle and between triangles, and also the desired situation where a river is present along one side of the triangle. The same situation can occur on one, two or all three sides of the triangle in cases such as lakes and coastal margins. For most geologic mapping from randomly located data the situation on the left is the preferred result. For topographic or geologically faulted surfaces however, the example on the right may be the required surface form. This causes problems!

Once the grid section (or complete grid) has been calculated the rows covered are written out to file.

TRIGRID outputs the Laser-Scan internal DTI (Digital Terrain Image) format DTM files which are the common file medium for the TVES (Terrain Visualisation and Exploitation Software) package.

Format converters are available to produce alternative DTM formats. Examples of such format conversions are UHL1 or TED4 type Defense Mapping Agency file format, or simple ASCII text listings.