On searching a contour map for a given terrain elevation profile

Abstract

This paper is concerned with the problem of using a digital computer to locate a ground track of known shape on a contour map, given the terrain elevation profile associated with the track. Such a problem is encountered, for example, when locating the ground track of an aircraft, given the elevation of the terrain below the aircraft during flight. The problem is characterized by the requirement to search for a specific solution out of an infinite number of possibilities. Exhaustive searching is impractical; therefore, what is needed is an efficient search strategy, suitable for programming on a digital computer, which will yield the solution in a reasonable time. The solution described takes advantage of the topological properties of the contour map. The given terrain elevation profile is first converted into a sequence of numbers describing the elevation values of the contour lines intersected by the unknown ground track. A graph of the map topology is then used to identify all the possible contour lines that could have been intersected by the ground track. Narrow bands are constructed, satisfying the topological constraints of the terrain elevation profile and the geometric constraints of the flight path. Results are based on actual computer map searches. © 1967.