Abstract: In the well-known Ramer-Douglas-Peucker (RDP) algorithm for polyline data compression, only the points with distance greater than a given tolerance from polyline (a chain of vertices) to segment (the first and last vertices of the polyline) are retained, while all other points on the original polyline are deleted. This gives rise to inconsistent data compression accuracy among the retained and the deleted points. In this paper, a new algorithm based on total least squares is presented, which takes each subset of a polyline as a processing unit and uses all the points on the original polyline to fit a new line. These fitted lines are intersected to form a final polyline, thus leading to improved compression accuracy. An experiment is included, which shows that compared with the traditional RDP algorithm, the proposed method has smaller approximation errors, especially for larger tolerance.

Key words: data compression, Ramer-Douglas-Peucker algorithm, total least squares