Incremental computation of planar maps

• Main Authors: Gangnet, M., Hervé, J.-C., Pudet, T., van Thong, J.-M.
• Format: Conference Proceeding
• Language: English
• Subjects: Applied computing > Arts and humanities > Fine arts; Applied computing > Arts and humanities > Performing arts; Computing methodologies > Computer graphics > Graphics systems and interfaces; Computing methodologies > Computer graphics > Shape modeling; Computing methodologies > Computer graphics > Shape modeling > Parametric curve and surface models; Computing methodologies > Computer graphics > Shape modeling > Volumetric models; Human-centered computing > Human computer interaction (HCI) > Interaction devices > Graphics input devices; Mathematics of computing > Mathematical analysis > Numerical analysis > Interpolation; Mathematics of computing > Probability and statistics > Probabilistic representations > Nonparametric representations > Spline models; Theory of computation > Randomness, geometry and discrete structures
• ISSN: 0097-8930
• DOI: 10.1145/74333.74369

A planar map is a figure formed by a set of intersecting lines and curves. Such an object captures both the geometrical and the topological information implicitly defined by the data. In the context of 2D drawing it provides a new interaction paradigm, map sketching, for editing graphic shapes.To build a planar map, one must compute curve intersections and deduce from them the map they define. The computed topology must be consistent with the underlying geometry. Robustness of geometric computations is a key issue in this process. We present a robust solution to Bézier curve intersection that uses exact forward differencing and bounded rational arithmetic. Then, we describe data structure and algorithms to support incremental insertion of Bézier curves in a planar map. A prototype illustration tool using this method is also discussed.