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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A hierarchical scheme for representing curves without self-intersections


    Contributors:


    Publication date :

    2001-01-01


    Size :

    545516 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    A Hierarchical Scheme for Representing Curves without Self-Intersections

    Ho, P.-S. / Kim, M.-H. / IEEE | British Library Conference Proceedings | 2001


    Method and Apparatus for Representing Road Intersections

    WEILAND MICHAEL / NYCZAK GREGORY / MCDONOUGH WILLIAM et al. | European Patent Office | 2015

    Free access

    Method and apparatus for representing road intersections

    WEILAND MICHAEL / NYCZAK GREGORY / MCDONOUGH WILLIAM et al. | European Patent Office | 2016

    Free access