Area collapse algorithm computing new curve of 2D geometric objects

• Autorzy: Buczek M. M.

Identyfikatory

DOI

10.1515/geocart-2017-0004

• Języki publikacji: EN

Abstrakty

EN

The processing of cartographic data demands human involvement. Up-to-date algorithms try to automate a part of this process. The goal is to obtain a digital model, or additional information about shape and topology of input geometric objects. A topological skeleton is one of the most important tools in the branch of science called shape analysis. It represents topological and geometrical characteristics of input data. Its plot depends on using algorithms such as medial axis, skeletonization, erosion, thinning, area collapse and many others. Area collapse, also known as dimension change, replaces input data with lower-dimensional geometric objects like, for example, a polygon with a polygonal chain, a line segment with a point. The goal of this paper is to introduce a new algorithm for the automatic calculation of polygonal chains representing a 2D polygon. The output is entirely contained within the area of the input polygon, and it has a linear plot without branches. The computational process is automatic and repeatable. The requirements of input data are discussed. The author analyzes results based on the method of computing ends of output polygonal chains. Additional methods to improve results are explored. The algorithm was tested on real-world cartographic data received from BDOT/GESUT databases, and on point clouds from laser scanning. An implementation for computing hatching of embankment is described.

Słowa kluczowe

EN

shape analysis; Polygon collapse; medial axis; geometry processing; spatial database

PL

analiza kształtu; geometria; przestrzenna baza danych

• Wydawca: Komitet Geodezji PAN
• Czasopismo: Geodesy and Cartography
• Rocznik: 2017
• Tom: Vol. 66, no. 1
• Strony: 23--44
• Opis fizyczny: Bibliogr. 35 poz., rys.

Twórcy

autor

Buczek M. M.

• AGH University of Science and Technology Department of Engineering Surveying and Civil Engineering 30 Mickiewicza St., 30-059 Krakow, Poland

Bibliografia

• [1] Aggarwal, A., Guibas, L. J., Saxe, J., and Shor, P. W. (1989). A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete & Computational Geometry, 4(6), 591–604. DOI:10.1007/BF02187749.
• [2] Aichholzer, O., Aurenhammer, F., Alberts, D., and Gärtner, B. (1996). A novel type of skeleton for polygons. In J. UCS The Journal of Universal Computer Science (pp. 752–761). Springer Berlin Heidelberg. DOI: 10.3217/jucs-001-12-0752.
• [3] Aichholzer, O., and Aurenhammer, F. (1996, June). Straight skeletons for general polygonal fi gures In the plane. In International Computing and Combinatorics Conference (pp. 117–126). Springer Berlin Heidelberg. DOI: 10.1007/3-540-61332-3_144.
• [4] Amenta, N., Choi, S., and Kolluri, R. K. (2001). The power crust, unions of balls, and the medial axis transform. Computational Geometry, 19(2), 127–153. Doi:10.1016/S0925-7721(01)00017-7.
• [5] Bader, M., and Weibel, R. (1997, June). Detecting and resolving size and proximity confl icts in the generalization of polygonal maps. In Proceedings 18th International Cartographic Conference (Vol. 23, p. 27).
• [6] Bharatkumar, A. G., Daigle, K. E., Pandy, M. G., Cai, Q., and Aggarwal, J. K. (1994, November). Lower limb kinematics of human walking with the medial axis transformation. In Motion of Non-Rigid and Articulated Objects, 1994., Proceedings of the 1994 IEEE Workshop on (pp. 70–76). doi: 10.1109/MNRAO.1994.346252.
• [7] Blum, H. (1967). A transformation for extracting new descriptors of shape. In: W. Wathen-Dunn (ed), Models for the Perceptionof Speech and Visual Form (pp. 362–380), MIT Press, Cambridge, MA.
• [8] Brandt, J. W., Jain, A. K., and Algazi, V. R. (1991). Medial axis representation and encoding of scanned documents. Journal of Visual Communication and Image Representation, 2(2), 151–165. DOI:10.1016/1047-3203(91)90005-Z.
• [9] Brandt, J. W. (1994). Convergence and continuity criteria for discrete approximations of the continuous planar skeleton. CVGIP: Image Understanding, 59(1), 116–124. DOI: 10.1006/ciun.1994.1007.
• [10] Bucksch, A., Lindenberg, R. C., and Menenti, M. (2009). Applications for point cloud skeletonizations in forestry and agriculture. Reports on Geodesy, 65-75.
• [11] Cherin, N., Cordier, F., and Melkemi, M. (2014). Modeling piecewise helix curves from 2D sketches. Computer-Aided Design, 46, 258–262. DOI: 10.1016/j.cad.2013.08.042.
• [12] Chin, F., Snoeyink, J., and Wang, C. A. (1999). Finding the medial axis of a simple polygon in linear time. Discrete & Computational Geometry, 21(3), 405–420. DOI: 10.1007/PL00009429.
• [13] Cordier, F., Melkemi, M., and Seo, H. (2016). Reconstruction of helices from their orthogonal projection. Computer Aided Geometric Design, 46, 1–15. DOI: 10.1016/j.cagd.2016.04.004.
• [14] Culver, T., Keyser, J., and Manocha, D. (2004). Exact computation of the medial axis of a polyhedron. Computer Aided Geometric Design, 21(1), 65–98. DOI: 10.1016/j.cagd.2003.07.008.
• [15] Dey, T. K., and Zhao, W. (2004). Approximate medial axis as a voronoi subcomplex. Computer-Aided Design, 36(2), 195-202. DOI: 10.1016/S0010-4485(03)00061-7.
• [16] Djidjev, H., and Lingas, A. (1991, August). On computing the Voronoi diagram for restricted planar figures. In Workshop on Algorithms and Data Structures (pp. 54–64). Springer Berlin Heidelberg. DOI: 10.1007/BFb0028250.
• [17] Dong, Z., Ting, Y., Xue, L., and Feng, A. (2015). Skeleton Extraction for Real Trees. International Journal of Advancements in Computing Technology, 7(4), 22.
• [18] Fogg, H. J., Armstrong, C. G., and Robinson, T. T. (2014). New techniques for enhanced medial axis based decompositions in 2-D. Procedia Engineering, 82, 162–174. DOI:10.1016/j.proeng.2014.10.381.
• [19] Haunert, J. H., and Sester, M. (2008). Area collapse and road centerlines based on straight skeletons. GeoInformatica, 12(2), 169–191. DOI: 10.1007/s10707-007-0028-x.
• [20] Kozioł, K., Szombara, S., and Knecht, J. (2012). Wyznaczenie punktów stałych obiektów przestrzennych na drodze automatycznej. Archiwum Fotogrametrii, Kartografi i i Teledetekcji, 23.
• [21] Lähner, Z., Rodola, E., Schmidt, F. R., Bronstein, M. M., and Cremers, D. (2016). Effi cient globalny optimal 2d-to-3d deformable shape matching. In Proceedings of the IEEE Conference on Komputer Vision and Pattern Recognition (pp. 2185–2193). DOI: 10.1109/CVPR.2016.240.
• [22] Lee, D. T. (1982). Medial axis transformation of a planar shape. IEEE Transactions on pattern analysis and machine intelligence, (4), 363–369. DOI: 10.1109/TPAMI.1982.4767267.
• [23] Lee, I. K. (2000). Curve reconstruction from unorganized points. Computer aided geometric design, 17(2), 161-177. DOI: 10.1016/S0167-8396(99)00044-8.
• [24] Lenda, G. (2006). Metody tworzenia i modyfi kacji funkcji sklejanych na potrzeby opisu kształtu obiektów obserwowanych punktowo. Geodezja/Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie, 12, 277–290.
• [25] Lenda, G., and Mirek, G. (2013). Parametrization of spline functions to describe the shape of shell structures. Geomatics and Environmental Engineering, 7(1), 65.
• [26] Loncaric, S. (1998). A survey of shape analysis techniques. Pattern recognition, 31(8), 983–1001. DOI:10.1016/S0031-2023(97)00122-2.
• [27] Pavlidis, T. (1980). Algorithms for shape analysis of contours and waveforms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2(4), 301–312. DOI:10.1109/TPAMI.1980.4767029.
• [28] Piuze, E., Kry, P. G., and Siddiqi, K. (2011, April). Generalized helicoids for modeling hair geometry. In Computer Graphics Forum (Vol. 30, No. 2, pp. 247–256). Blackwell Publishing Ltd., DOI:10.1111/j.1467-8659.2011.01856.x.
• [29] GESUT 2015 – Rozporządzenie Ministra Administracji i Cyfryzacji z dnia 21 października 2015 r. w sprawie powiatowej bazy GESUT i krajowej bazy GESUT.
• [30] BDOT 2015 – Rozporządzenie Ministra Administracji i Cyfryzacji z dnia 2 listopada 2015 r. w sprawie bazy danych obiektów topografi cznych oraz mapy zasadniczej.
• [31] Sarfraz, M., Samreen, S., and Hussain, M. Z. (2016, March). Modeling of 2D objects with weighted-Quadratic Trigonometric Spline. In Computer Graphics, Imaging and Visualization (CGiV), 2016. 13th International Conference on (pp. 29–34). IEEE.
• [32] Shamos, M. I., and Hoey, D. (1975, October). Closest-point problems. In Foundations of Komputer Science, 1975., 16th Annual Symposium on (pp. 151–162).
• [33] Szombara, S. (2013). Transformation of areal objects into linear objects, regarding the map scale. Geoinformatica Polonica, 12, 25–34, DOI: 10.2478/v10300-012-0010-5.
• [34] Voronoï, G. (1908). Nouvelles applications des paramètres continus à la théorie des forms quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs. Journal für die reine und angewandte Mathematik, 134, 198–287.
• [35] Willcocks, C., Jackson, P., Nelson, C., and Obara, B. (2016). Extracting 3D Parametric Curves from 2D Images of Helical Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence. DOI: 10.1109/TPAMI.2016.2613866.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)