A hierarchical scheme for representing curves without self-intersections

A hierarchical representation scheme for planar curves is proposed, which provides natural approximation and efficient localization. The scheme uses the iterative end-point fit algorithm (or Douglas-Peucker algorithm (D.H. Douglas and T.K. Peucker, 1973)), but approximation errors are adjusted by force to eliminate unnatural approximations. The error adjustment just makes the approximation error of a node in a hierarchical tree less than or equal to those of its ancestor. A self-intersection resolving algorithm is also developed to remove self-intersections in all the possible approximations for a curve, which uses the cross-link technique to reduce computation time remarkably. In point of localization, the bounding area of a curve is represented as a minimum bounding octangle (MBO), which can enclose the curve compactly. The MBO satisfies the hierarchical inclusion property which is useful for hierarchical geometrical operations, such as the polygon intersection test and the point-inclusion test. Through several experiments, we found that the proposed scheme always generated curve approximations without self-intersections and provided more natural representations than other hierarchical representation schemes such as the strip tree, the arc tree, and the HAL tree.