Fast algorithm for generating sorted contour strings

Automatic generation of contours for graphical display and map plotting has been studied extensively since the early days of computing. The individual segments making up a contour line are often determined by subdividing the object of interest into small triangles and computing the contours assuming a linear variation on each triangle. However, efficient storage of contour data and the need to place labels (automatically) or to smooth the contours require that the contours be generated in continuous strings of segments. A simple approach to generate such strings is to sort the randomly generated contour segments. Since sorting can be time-consuming, the majority of previous approaches are contour-tracing algorithms that traverse the surface and generate the contour in a continuous sequence of segments. In this paper, we present a new sorting algorithm. The algorithm is relatively easy to implement, can be applied to any type of surface, and works for both 2D and 3D objects. The algorithm is significantly faster than the contour tracing approach, particularly when large numbers of segments are involved. (C) 2000 Elsevier Science Ltd. All rights reserved.