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.
A hierarchical scheme for representing curves without self-intersections
01.01.2001
545516 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
A Hierarchical Scheme for Representing Curves without Self-Intersections
British Library Conference Proceedings | 2001
|Method and Apparatus for Representing Road Intersections
Europäisches Patentamt | 2015
|Method and apparatus for representing road intersections
Europäisches Patentamt | 2016
|