Line simplification algorithm implementation and error analysis

摘要

Four line simplification algorithms such as step algorithm, line segment filtering algorithm, perpendicular distance algorithm and Douglas-Percker algorithm are discussed and implemented by programming based on dxf format file. The simplification rates of different algorithms under different thresholds are also analyzed. The points position errors and mean errors of different algorithms on similar simplification rate are also achieved. The results show that, for the same or similar simplification rate, Douglas - Percker algorithm has the lowest error, followed by the perpendicular distance algorithm. For a given line, determining an appropriate threshold need repeated practice by step algorithm and line segment filtering algorithm, and the maximum permissible error can generally meet precision for Douglas-Percker algorithm and perpendicular distance algorithm.