Landscape Editor - Interpolation

Overview
This tool will interpolate the heights of undefined (null) sample points. After defining a representative sample of points, for example along contour lines, this facility enables heights to be derived for the remaining undefined points. This version of GenesisII offers two interpolation algorithms, an implementation of the Natural Neighbour algorithm (nngridr), which should be used to interpolate the majority of missing heights, and a trend analysis/smoothing transform, which should be used for filling in the last few points once the majority of heights have been interpolated.

The Interpolation Process
You should broadly follow the steps outlined below:

Define a representative set of points, for example using the spot height and contour line tools. See the item on interpolation considerations below for more information.

1. Select the interpolation tool from the button bar and click and drag to define an area to be interpolated. After the mouse button is released a dialog box will be displayed to confirm that interpolation is to be started. Fill in the appropriate parameters for nearest neighbour interpolation (see below, but these will be the defaults when using the interpolation tool for the first time) and press OK to commence. Whilst calculating a dialog box will be displayed showing progress and allowing cancellation of the calculation.
2. If possible it is best to interpolate all points in one calculation. GenesisII has no practical limit on the number of grid points that may be interpolated. However in cases where interpolation is to be used to 'fill in' missing areas from a map (for example, to recalculate heights after altering an area of a landscape) smaller areas can be processed individually. In all cases however you should aim to fill in 95% or more of all points using Nearest Neighbour interpolation.
3. Finally, if there are any missing points, or you wish to smooth the surface, click the mouse anywhere on the canvas to start interpolation again. Select the Trend Analysis/Smoothing radio button, set the check boxes as required to apply trend analysis and/or smoothing, then click on OK. Both trend analysis and smoothing apply to all grid points.

The Interpolate Heights Dialog
The following parameters may be set:

• Use Nearest Neighbour/Trend Analysis. This pair of radio buttons determines which interpolation algorithm will be used. Controls not used by an algorithm will be disabled.
• Use calculated gradients. Used by Nearest Neighbour interpolation. Defaults to ON. Uses gradients to estimate the trends in the data when checked. For example, a rounded hilltop will be deduced if points are available around a hill, but not on top. If turned off gradients will not be used and a flat top will be deduced.
• Optimise for speed. Used by Nearest Neighbour interpolation. Defaults to ON. Calculates faster by making more generous usage of memory. When turned off requires less memory but is significantly slower.
• Extrapolate. Used by Nearest Neighbour interpolation. Defaults to OFF. Enables extrapolation when checked. This is by its nature a tenuous proposition, and should be used with caution after the majority of the map heights have been defined directly or by interpolation. Note that it is advisable to define as many grid points as possible on the edges of the map, and particularly at the corners, as this reduces the amount of extrapolation required.
• Tautness Parameters #1 and #2. Used by Nearest Neighbour interpolation. These two parameters control the 'taughtness' of the generated surface around the points already defined. Increasing the value of parameter 1 increases the influence of the gradient, increasing the value of parameter 2 increases the area over which the influence of the gradient is felt. Reasonable ranges are 1 to 3 for parameter #1, and 5 - 12 for parameter #2.
• Minimum Height. Used by both interpolation methods. The minimum height setting is available to help when defining sea coasts and other areas of water. For example, to define an island draw the appropriate contour lines and spot heights for the island and an area of sea at zero height for two or more sample points around the coast before applying interpolation.
• Trend Analysis. Used by Trend Analysis interpolation. Defaults to ON. Applies a trend analysis to the whole grid to fill in any undefined points.
• Smoothing Transform. Used by Trend Analysis interpolation. Defaults to ON. Applies a smoothing algorithm to the whole grid to correct any anomalous points.

Interpolation Considerations
The proportion of defined to undefined sample points required depends on the kind of landscape being defined. For smooth, rounded hills or plains reasonable results may be obtained with 1 point in 40 or less. For more complex structures 1 in 20 or less is recommended. Interpolation is most accurate where the surface has few discontinuities - so for a valley with steep sides and a flat bottom placing defined points along the sides will be sufficient to derive the shape of the sides. However, without further information the interpolation function will assume a continuation of the sides to form an over-deepened 'V', so you will need to define some of the valley floor.

In some circumstances the nearest neighbour interpolation algorithm will be unable to proceed and an error message will be displayed: for example if the height to width ration of the selected area is too extreme. Re-select and try again.

nngridr and Calculation Efficiency
The implementation of the nearest neighbour algorithm used in GenesisII was developed by Dave Watson (contact PO Box 734 Claremont, WA 6010, Australia). This is probably one of the most effective algorithms of it's type available. However, although yielding excellent results, the time required to calculate interpolated values varies approximately with the square of the number of points. We found that in practice on a Pentium-90 an area of up to about 10,000 points could be calculated with a delay of only a few minutes, and calculations on up to 160,000 points or more are certainly feasible if you are willing to allow for the time required.

Calculation times can be improved by dividing a large area into several smaller ones and interpolating in a stepwise manner, but in practise this is not recommended as artefacts may be produced around the edges of these areas (although these can be minimised by ensuring a good overlap).