AUTOMATED REASONING WITH CONTOUR MAPS

An extension of binary search into two dimensions is applied to the issue of automated interpretation of contour maps. A contour map, more formally known as a topographic line map, may be perceived as a hierarchy of nested contours. Once a map is organized into a sorted data structure termed a contour containment graph, the power of binary search may be invoked to achieve O(log n) time complexity during a topographical query, where n is the number of contours that comprise a specific map subdivision. A topographical query is a request by a user to interpret the position of an arbitrary coordinate, termed the query point, in the context of a contour map background. An ''interpretation'' is defined to be five pieces of information: the label of the map subdivision within which the query point resides; the topographical contour of the subdivision that encloses the query point; the local elevation at the point; and the two components of slope at the point-the gradient and aspect angle. An investigation of the tradeoff in precision and performance of:he new algorithm is included, in the context of contoured versus gridded representations of terrain. It is suggested that the best features of the contour approach be integrated with the best features of algorithms which process gridded digital elevation models.