ABSTRACT. All digitizing methods, as a general rule, record lines with far more data than is necessary for accurate graphic reproduction or for computer analysis. Two algorithms to reduce the number of points required to represent the line and, if desired, produce caricatures, are presented and compared with the most promising methods so far suggested. Line reduction will form a major part of automated generalization. Lines from maps and photographs are recorded numerically for cartographic manipulation to facilitate their reproduction at different scales and projections, and to allow map compilation with other geographic data bases. Usually lines are approximated by straight line segments, and end points of which are recorded by a pair of co-ordinates in either polar or orthogonal measure. The other more important methods by which lines are recorded are chain encoding and skeleton encoding. Chains approximate lines by a sequence of end to end vectors, where the length and direction of the vectors are selected from a fixed, usually four or eight, number of possibilities.1 Skeleton encoding is directed more at recording closed areas or polygons by filling the area with circles or rhombi of different sizes. The lines forming the boundaries are recorded by implication." The conversion of graphic data to computer readable numerical forms is effected with a co-ordinate digitizer. a bit plane scanner or an automatic line follower. A co-ordinate digitizer converts a pointer's location on a table to x-y values which can be written on punched cards or magnetic devices. Polar co-ordinate digitizers, which consist of a slide in a rotating anchor head, record a radius and an angle from a base vector. Another digitizing dev~ce consists of a pointer suspended from a pair of retracting wires which activate potentiometers. Conversion of values in one recording co-ordinate system to another can --be performed easily with small computer programs. Drum scanners superimpose a vast and very fine grid over the document to be digitized recording a "yes-no" or "on-off value for each cell location, depending on whether that cell covers a line or not. A tradeoff is introduced between the fineness of the mesh, implying more computer processing time to reduce the data to forms which are easily handled, and coarseness of the image recorded. On the other hand, the mesh density, being dependent on hardware, is fixed at the time of manufacture and is usually set to be somewhat smaller than the minimum line width. In all cases, the reduction of a bit plane scan, in which lines are represented by clouds of cells containing numerous discontinuities, to chain or vector encoded lines, is a complex process requiring processing time and resources which could only be described as being quite substantial. With a co-ordinate digitizer lines may be recorded in point mode, time or increment automatic modes. Lines recorded in point mode are effectively generalized by the operator who subjectively selects points which best approximate the line to the degree he desires. This presumes, among other things, that he is his own customer. Point digitizing is extremely tedious however, and is unsuitable for anything but the simplest data sets, such as the generalized David H.
Douglas and Peucker were amongst the first to propose an algorithm for reducing the number of points in a digital trajectory REF .