×

Arrangements on parametric surfaces. I: General framework and infrastructure. (English) Zbl 1205.68457

Summary: We introduce a framework for the construction, maintenance, and manipulation of arrangements of curves embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The framework applies to planes, cylinders, spheres, tori, and surfaces homeomorphic to them. We reduce the effort needed to generalize existing algorithms, such as the sweep line and zone traversal algorithms, originally designed for arrangements of bounded curves in the plane, by extensive reuse of code. We have realized our approach as the Cgal package Arrangement_on_surface_2. We define a compact and modular interface for our framework; for a given application a required small subset of the interface can be identified. Then, only this subset must be implemented. A companion paper describes concretizations for several types of surfaces and curves embedded on them, and applications. This is the first implementation of a generic algorithm that can handle arrangements on a large class of parametric surfaces.
[For Part II, cf. ibid. 4, No. 1, 67–91 (2010; Zbl 1205.68456)].

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
14Q10 Computational aspects of algebraic surfaces

Citations:

Zbl 1205.68456
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] The Cgal Project: Cgal User and Reference Manual. Cgal Editorial Board, 3.7 edn. http://www.cgal.org/Manual/3.7/doc_html/cgal_manual/contents.html (2010)
[2] Agarwal P.K., Sharir M.: Arrangements and their applications. In: Sack, J.-R., Urrutia, J. (eds) Handbook of Computational Geometry, chap. 2, pp. 49–119. Elsevier, Amsterdam (2000) · Zbl 0948.52011
[3] Andrade M.V.A., Stolfi J.: Exact algorithms for circles on the sphere. Int. J. Comput. Geometry Appl. 11(3), 267–290 (2001) · Zbl 1074.68626
[4] Austern M.H.: Generic Programming and the STL. Addison-Wesley, New York (1999)
[5] Bentley J.L., Ottmann T.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9), 643–647 (1979) · Zbl 0414.68074
[6] Berberich, E., Emeliyanenko, P.: Cgal’s curved kernel via analysis. Algorithms for complex shapes. Technical report ACS-TR-123203-04 (2008)
[7] Berberich, E., Fogel, E., Halperin, D., Kerber, M., Setter, O.: Arrangements on parametric surfaces II: concretization and applications. Math. Comput. Sci. (2010, accepted) · Zbl 1205.68456
[8] Berberich, E., Fogel, E., Halperin, D., Mehlhorn, K., Wein, R.: Sweeping and maintaining two-dimensional arrangements on surfaces: a first step. In: Proceedings 15th Annual Eurpean Symposium on Algorithms (ESA), LNCS, vol. 4698, pp. 645–656. Springer-Verlag, Berlin (2007) · Zbl 1151.68700
[9] Berberich, E., Hemmer, M., Kettner, L., Schömer, K., Wolpert, N.: An exact, complete and efficient implementation for computing planar maps of quadric intersection curves. In: Proceedings of 21st Annual Symposium on Computational Geometry (SoCG), pp. 99–106. ACM Press, New York (2005) · Zbl 1387.68237
[10] Berberich, E., Kerber, M.: Exact arrangements on tori and Dupin cyclides. In: Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling (SPM), pp. 59–66. ACM Press, New York (2008)
[11] Brisson, E.: Representing geometric structures in d dimensions: topology and order. In: SCG ’89: Proceedings of the Fifth Annual Symposium on Computational Geometry, pp. 218–227. ACM, New York (1989)
[12] Cazals F., Loriot S.: Computing the arrangement of circles on a sphere, with applications in structural biology. Comput. Geom. Theory Appl. 42(6–7), 551–565 (2009) · Zbl 1167.65336
[13] Cazals F., Loriot S.: Computing the arrangement of circles on a sphere, with applications in structural biology. Comput. Geom. Theory Appl. 42(6–7), 551–565 (2009) · Zbl 1167.65336
[14] de Castro P.M.M., Cazals F., Loriot S., Teillaud M.: Design of the CGAL 3D Spherical Kernel and application to arrangements of circles on a sphere. Comput. Geom. Theory Appl. 42(6–7), 536–550 (2009) · Zbl 1169.65021
[15] Edelsbrunner H., Seidel R.: Voronoi diagrams and arrangements. Disc. Comput. Geom. 1, 25–44 (1986) · Zbl 0598.52013
[16] Eigenwillig, A., Kerber, M.: Exact and efficient 2D-arrangements of arbitrary algebraic curves. In: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 122–131, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics (SIAM) (2008) · Zbl 1192.14047
[17] Fabri A., Giezeman , Lutz Kettner G.-J., Schirra S., Schönherr S.: On the design of Cgal a computational geometry algorithms library. Softw. Pract. Exp. 30(11), 1167–1202 (2000) · Zbl 1147.68781
[18] Fogel E., Halperin D., Kettner L., Teillaud M., Wein R., Wolpert N.: Arrangements. In: Boissonnat, J.-D., Teillaud, M. (eds) Effective Computational Geometry for Curves and Surfaces, chap. 1, pp. 1–66. Springer-Verlag, Berlin (2007)
[19] Fogel, E., Setter, O., Halperin, D.: Exact implementation of arrangements of geodesic arcs on the sphere with applications. In: Abstracts of the 24th European Workshop on Computational Geometry, pp. 83–86 (2008)
[20] Fogel, E., Setter, O., Halperin, D.: Movie: Arrangements of geodesic arcs on the sphere. In: Proceedings of 24th Annual ACM Symposium on Computational Geometry (SoCG), pp. 218–219. ACM Press, New York (2008) · Zbl 1221.65064
[21] Gamma E., Helm R., Johnson R., Vlissides J.: Design Patterns–Elements of Reusable Object-Oriented Software. Addison-Wesley, New York (1999) · Zbl 0887.68013
[22] Halperin, D.: Arrangements. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, chap. 24, 2nd edn., pp. 529–562. Chapman & Hall/CRC (2004)
[23] Halperin D., Shelton C.R.: A perturbation scheme for spherical arrangements with application to molecular modeling. Comput. Geom. Theory. Appl. 10, 273–287 (1998) · Zbl 0904.68173
[24] Hemmer, M.: Exact computation of the adjacency graph of an arrangement of quadrics. Ph.D. thesis, Johannes-Gutenberg-Universität, Mainz, Germany (2008)
[25] Hijazi, Y.O., Breuel, T.M.: Computing arrangements using subdivision and interval arithmetic. In: Proceedings of 6th International Conference on Curves and Surfaces, pp. 173–182 (2006) · Zbl 1130.65042
[26] Lazarus, F., Pocchiola, M., Vegter, G., Verroust, A.: Computing a canonical polygonal schema of an orientable triangulated surface. In: Proceedings of 17th Annual ACM Symposium on Computational Geometry (SoCG), pp. 80–89 (2001) · Zbl 1378.65060
[27] Mehlhorn, K., Näher, S.: Leda: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge (2000) · Zbl 0976.68156
[28] Mehlhorn K., Seel M.: Infimaximal frames: A technique for making lines look like segments. Int. J. Comput. Geometry Appl. 13(3), 241–255 (2003) · Zbl 1093.68131
[29] Meyerovitch, M.: Robust, generic and efficient construction of envelopes of surfaces in three-dimensional space. In: Proceedings of 14th Annual European Symposium on Algorithms (ESA), LNCS, vol. 4168, pp. 792–803. Springer-Verlag, Berlin (2006) · Zbl 1131.68566
[30] Milenkovic V., Sacks E.: An approximate arrangement algorithm for semi-algebraic curves. Int. J. Comput. Geom. Appl. 17(2), 175–198 (2007) · Zbl 1144.65014
[31] Setter, O., Sharir, M., Halperin, D.: Constructing two-dimensional Voronoi diagrams via divide-and-conquer of envelopes in space. In: Proceedings of 6th Annual International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pp. 43–52 (2009) · Zbl 1309.68206
[32] Wein R., Fogel E., Zukerman B., Halperin D.: Advanced programming techniques applied to Cgal’s arrangement package. Comput. Geom. Theory Appl. 38(1–2), 37–63 (2007) Special issue on Cgal · Zbl 1114.65312
[33] Wein, R., Fogel, E., Zukerman, B., Halperin, D.: 2D arrangements. In: Cgal User and Reference Manual. Cgal Editorial Board, 3.7 edn. http://www.cgal.org/Manual/3.7/doc_html/cgal_manual/packages.html#Pkg:Arrangements2 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.