An optimal O(n) algorithm for identifying line segments from a sequence of chain codes

摘要

An optimal algorithm for identifying straight lines in chain codes is described. The algorithm turns the complicated problem of determining the straightness of digital arcs into a simple task by constructing a passing area around the pixels. It also solves the problem of detecting all straight segments from a sequence of chain codes in O(n) time, where n is the length of the sequence. It has been found that this algorithm is not only simple and intuitive, but also highly efficient.