Optimal polygonal approximation of digital curves

摘要

An algorithm for optimal polygonal approximation is presented. Given a value for the maximal allowed distance between the approximation and the curve, the algorithm finds an approximation with the minimal number of vertices. The city-block metric is used to measure the distance between the approximation and the curve. The algorithm worst case complexity is O(n2), where n is the number of points in the curve. An efficient and optimal solution for the case of closed curves where no initial point is given, is also presented.