“Incremental computation of planar maps” by Gangnet, Herve, Pudet and van Thong

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.

1. D. Baroni. Art Graphique Design. Editions du Chine, Paris, 1987.
2. P. Baudelaire and M. Gangnet. Planar Maps: an Interaction Paradigm for Graphic Design. In CHI’89 Proceedings, Addison-Wesley, 1989.
3. J.L. Bentley and T.A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Trans. on Comput., 28(9), 1979.
4. T.D. DeRose and B.A. Barsky. Geometric Continuity for Catmull-Rom Splines. ACM Transactions on Graphics, 7(1), 1988.
5. D.H. Greene and F.F. Yao. Finite-Resolution Computational Geometry. In Proc. 27th IEEE Syrup. on Found. Comp. Sci., Toronto, 1986.
6. D. Dobkin and D. Silver. Recipes for Geometry and Numerical Analysis. In Proceedings of the Fourth Annual ACM Symposium on Computational Geometry, ACM Press, New York, 1988.
7. H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, New York, 1987.
8. H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir. Calculating Arrangements of Segments, Circles, or Other Curves in the Plane. 1988. Submitted for publication.
9. H. Edelsbrunner and L.J. Guibas. Topologically Sweeping an Arrangement. Research Report #9, Digital Equipment Systems Research Center, Palo Alto, 1986.
10. A. R. Forrest. Geometric Computing Environments: Some Tentative Thoughts. In Theoretical Foundations of Computer Graphics and CAD, Springer-Verlag, 1988.
11. M. Gangnet and J.C. Herv6. D2: un 6diteur graphique interactif. In Acres des Journdes SM90, Eyrolles, Paris, 1985.
12. L. Guibas and J. Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 4(2), 1985.
13. C.M. Hoffmann, J.E. Hopcroft, and M.S. Karasick. Towards Implementing Robust Geometric Computations. In Proceedings of the Fourth Annual ACM Symposium on Computational Geometry, ACM Press, New York, 1988.
14. P.A. Koparkar and S.P. Mudur. A new class of algorithms for the processing of parametric curves. Computer-Aided Design, Vot. 15, 1983.
15. J.F. Lane. Curve and Surface Display Techniques. Tutorial, ACM SIGGRAPH’81,1981.
16. S.L. Lien, M. Shantz, and V. Pratt. Adaptive Forward Differencing for Rendering Curves and Surfaces. ACM Computer Graphics, Vol. 21(4):111-118, 1987.
17. P. Lienhardt. Extensions of the Notion of Map and Subdivision of a Three-Dimensional Space. In STACS’88, Lecture Notes in Computer Science 294, 1988.
18. D. Michelucci. Th~se. Ecole Nationale Suprrieure des Mines de Saint-Etienne, Saint-Etienne, 1987.
19. D. Michelucci and M. Gangnet. Saisie de p~ans ~t partir de tracrs ~ main-levre. In Actes de MICAD 84, Hennas, Paris, 1984.
20. F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, New York, 1985.
21. L. Ramshaw. Blossoming: A Connect-the-Dots Approach to Sptines. Research Report # 19, Digital Equipment Systems Research Center, Palo Alto, 1987.
22. M.H. Schultz. Sptine Analys&. Prentice Hall, 1973.
23. T.W. Sederberg and S.R. Parry. Comparison of three curve intersection algorithms. Computer-Aided Design, Vol. 18, 1986.
24. W.T. Tutte. Graph Theory. Addison-Wesley, 1984.
25. G. Wang. The Subdivision Method for Finding the Intersection between two B6zier Curves or Surfaces. Zhejiang UniversiO, Journal, 1984. Cited in reference {23}.