{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T12:38:30Z","timestamp":1775738310663,"version":"3.50.1"},"reference-count":55,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T00:00:00Z","timestamp":1551225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>In spatial science, the relationship between spatial objects is considered to be a vital element. Currently, 3D objects are often used for visual aids, improving human insight, spatial observations, and spatial planning. This scenario involves 3D geometrical data handling without the need for topological information. Nevertheless, in the near future, users will shift to more complex queries corresponding to the existing 2D spatial approaches. Therefore, having 3D spatial objects without having these relationships or topology is impractical for 3D spatial analysis queries. In this paper, we present a new method for creating topological information that we call the Compact Abstract Cell Complexes (CACC) data structure for 3D spatial objects. The idea is to express in the most compact way the topology of a model in 3D (or more generally in nD) without requiring the topological space to be discrete or geometric. This is achieved by storing all the atomic cycles through the models (null combinatorial homotopy classes). The main idea here is to store the atomic paths through the models as an ant experiences topology: each time the ant perceives a previous trace of pheromone, it knows it has completed a cycle. The main advantage of this combinatorial topological data structure over abstract simplicial complexes is that the storage size of the abstract cell cycles required to represent the geometric topology of a model is far lower than that for any of the existing topological data structures (including abstract simplicial cell cycles) required to represent the geometric decomposition of the same model into abstract simplicial cells. We provide a thorough comparative analysis of the storage sizes for the different topological data structures to sustain this.<\/jats:p>","DOI":"10.3390\/ijgi8030102","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T11:41:03Z","timestamp":1551267663000},"page":"102","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Abstract Topological Data Structure for 3D Spatial Objects"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5281-8478","authenticated-orcid":false,"given":"Uznir","family":"Ujang","sequence":"first","affiliation":[{"name":"Faculty of Built Environment and Surveying, Universiti Teknologi Malaysia, Johor Bahru  81310, Johor, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesc","family":"Anton Castro","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences and Information Technology Yachay Tech University, San Miguel de Urcuqu\u00ed, Hacienda San Jos\u00e9 s\/n, Imbabura, Ecuador"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suhaibah","family":"Azri","sequence":"additional","affiliation":[{"name":"Faculty of Built Environment and Surveying, Universiti Teknologi Malaysia, Johor Bahru  81310, Johor, Malaysia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,2,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2842","DOI":"10.3390\/ijgi4042842","article-title":"Applications of 3D City Models: State of the Art Review","volume":"4","author":"Biljecki","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.cageo.2017.02.008","article-title":"Augmenting comprehension of geological relationships by integrating 3D laser scanned hand samples within a GIS environment","volume":"103","author":"Harvey","year":"2017","journal-title":"Comput. Geosci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/j.eswa.2016.01.037","article-title":"A 3D GIS-based interactive registration mechanism for outdoor augmented reality system","volume":"55","author":"Huang","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_4","unstructured":"Tan, Y., Takagi, H., and Shi, Y. (August, January 27). Development of 3D Earth Visualization for Taiwan Ocean Environment Demonstration. Proceedings of the Data Mining and Big Data: Second International Conference, DMBD 2017, Fukuoka, Japan."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1016\/j.compenvurbsys.2017.04.001","article-title":"Street level urban design qualities for walkability: Combining 2D and 3D GIS measures","volume":"64","author":"Yin","year":"2017","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Mohd, Z.H., Ujang, U., and Choon, T.L. (2017). Heritage House Maintenance using 3D City Model Application Domain Extension Approach. Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci., 73\u201376.","DOI":"10.5194\/isprs-archives-XLII-4-W6-73-2017"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"201","DOI":"10.5194\/isprs-archives-XLII-4-W10-201-2018","article-title":"Urban Heat Island Micro-Mapping via 3D City Model","volume":"XLII-4\/W10","author":"Ujang","year":"2018","journal-title":"Int. Arch. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_8","first-page":"1","article-title":"Navigating Spatial Relationships in Oceania","volume":"9","author":"Feinberg","year":"2016","journal-title":"Struct. Dyn."},{"key":"ref_9","unstructured":"Nagaraja, T.N., Keenan, K., Irtenkauf, S., Hasselbach, L., Panda, S., Cabral, G., Ewing, J.R., Mikkelsen, T., and de Carvalho, A. (2016, January 16\u201320). A method to examine spatial relationships between tumor cells and vasculature using a mouse orthotopic PDX glioblastoma model. Proceedings of the AACR 107th Annual Meeting 2016, New Orleans, LA, USA."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.compind.2016.04.005","article-title":"MESSRS: A model-based 3D system for of recognition, semantic annotation and calculating the spatial relationships of a factory\u2019s digital facilities","volume":"82","year":"2016","journal-title":"Comput. Ind."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.ssci.2015.09.021","article-title":"Modeling spatial relationships between multimodal transportation infrastructure and traffic safety outcomes in urban environments","volume":"82","author":"Tasic","year":"2016","journal-title":"Saf. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Waters, N. (2016). Tobler\u2019s First Law of Geography, International Encyclopedia of Geography: People, the Earth, Environment and Technology, John Wiley & Sons, Ltd.","DOI":"10.1002\/9781118786352.wbieg1011"},{"key":"ref_13","unstructured":"Claudia, S., and Volker, C. (2008, January 4\u20136). Development of Citygml ADE for Dynamic Flood Information. Proceedings of the 3rd International ISCRAM China Workshop, Harbin, China."},{"key":"ref_14","unstructured":"Xu, Z., Zhu, G., Wu, X., and Yan, H. (2007). 3D Modeling of Groundwater Based on Volume, Advances in Spatio-Temporal Analysis, Taylor Francis Group."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/17480930.2013.828443","article-title":"3D GIS for mine development\u2014Integrated concepts","volume":"29","author":"Duncan","year":"2015","journal-title":"Int. J. Min. Reclam. Environ."},{"key":"ref_16","unstructured":"Katerina, K., Maria, K., Aggeliki, K., Konstantinos, G.N., Nikolaos, S., and Nikolaos, D. (2016, January 4\u20138). 3D subsurface geological modeling using GIS, remote sensing, and boreholes data. Proceedings of the Fourth International Conference on Remote Sensing and Geoinformation of the Environment, Paphos, Cyprus."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.compenvurbsys.2016.04.005","article-title":"An improved LOD specification for 3D building models","volume":"59","author":"Biljecki","year":"2016","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Breunig, M., Al-Doori, M., Butwilowski, E., Kuper, P.V., Benner, J., and Haefele, K.H. (2015). Generalization of 3D IFC Building Models. 3D Geoinformation Science: The Selected Papers of the 3D GeoInfo 2014, Springer International Publishing.","DOI":"10.1007\/978-3-319-12181-9"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1055","DOI":"10.3390\/ijgi4031055","article-title":"Modeling a 3D City Model and Its Levels of Detail as a True 4D Model","volume":"4","author":"Ohori","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Ivan, I., Singleton, A., Hor\u00e1k, J., and Inspektor, T. (2017). Compression of 3D Geographical Objects at Various Level of Detail. The Rise of Big Spatial Data, Springer International Publishing.","DOI":"10.1007\/978-3-319-45123-7"},{"key":"ref_21","unstructured":"Floriani, L.D., Fellegara, R., and Magillo, P. (2010, January 2\u20135). Spatial indexing on tetrahedral meshes. Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, San Jose, CA, USA."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1603","DOI":"10.1109\/TVCG.2009.186","article-title":"Supercubes: A High-Level Primitive for Diamond Hierarchies","volume":"15","author":"Weiss","year":"2009","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bertolotto, M., Floriani, L.D., and Marzano, P. (1995, January 21\u201323). A Unifying Framework for Multilevel Description of Spatial Data. Proceedings of the COSIT, Semmering, Austria.","DOI":"10.1007\/3-540-60392-1_17"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.cviu.2003.11.003","article-title":"Topological properties of closed digital spaces: One method of constructing digital models of closed continuous surfaces by using covers","volume":"102","author":"Evako","year":"2006","journal-title":"Comput. Vis. Image Underst."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0166-218X(02)00222-6","article-title":"Multidimensional cell lists for investigating 3-manifolds","volume":"125","author":"Kovalevsky","year":"2003","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/S0065-2539(08)61037-9","article-title":"Finite Topology and Image Analysis. Adv","volume":"84","author":"Kovalevsky","year":"1992","journal-title":"Electron. Electron Phys."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3485","DOI":"10.1016\/j.dam.2009.04.008","article-title":"Polyhedral approximation and practical convex hull algorithm for certain classes of voxel sets","volume":"157","author":"Schulz","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/S0304-3975(02)00712-0","article-title":"Cell complexes, oriented matroids and digital geometry","volume":"305","author":"Webster","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"3424","DOI":"10.1016\/j.dam.2009.04.016","article-title":"Thinning on cell complexes from polygonal tilings","volume":"157","author":"Wiederhold","year":"2009","journal-title":"Discret. Appl. Math."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Fomenko, A.T. (1994). Visual Geometry and Topology, Springer Science & Business Media.","DOI":"10.1007\/978-3-642-76235-2"},{"key":"ref_31","unstructured":"Klette, R. (August, January 30). Cell complexes through time. Proceedings of the Vision Geometry IX, International Symposium on Optical Science and Technology, San Diego, CA, USA."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.compenvurbsys.2017.01.001","article-title":"Generating 3D city models without elevation data","volume":"64","author":"Biljecki","year":"2017","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Abdul-Rahman, A. (2017). Managing Versions and History Within Semantic 3D City Models for the Next Generation of CityGML. Advances in 3D Geoinformation, Springer International Publishing.","DOI":"10.1007\/978-3-319-25691-7"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.compenvurbsys.2016.12.005","article-title":"The influence of data quality on urban heating demand modeling using 3D city models","volume":"64","author":"Nouvel","year":"2017","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1080\/17538947.2016.1205673","article-title":"Using modular 3D digital earth applications based on point clouds for the study of complex sites","volume":"9","author":"Verhoeven","year":"2016","journal-title":"Int. J. Digit. Earth"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/j.cag.2015.07.008","article-title":"Automatic reconstruction of parametric building models from indoor point clouds","volume":"54","author":"Ochmann","year":"2016","journal-title":"Comput. Graph."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"107","DOI":"10.5194\/isprs-annals-IV-2-W1-107-2016","article-title":"Using a Space Filling Curve Approach for the Management of Dynamic Point Clouds","volume":"4","author":"Psomadaki","year":"2016","journal-title":"ISPRS Ann. Photogramm. Remote Sens. Spat. Inf. Sci."},{"key":"ref_38","unstructured":"Gerhard, G., Thomas, H.K., Angela, C., and Claus, N. (2008). OpenGIS City Geography Markup Language (CityGML) Encoding Standard, Open Geospatial Consortium."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1109\/38.364963","article-title":"Nonmanifold topology based on coupling entities","volume":"15","author":"Yamaguchi","year":"1995","journal-title":"IEEE Comput. Graph. Appl."},{"key":"ref_40","first-page":"3","article-title":"The radial edge structure: A topological representation for nonmanifold geometric boundary modeling","volume":"1","author":"Weiler","year":"1988","journal-title":"Geom. Model. CAD Appl."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Lee, S.H., and Lee, K. (2001, January 4\u20138). Partial entity structure: A compact non-manifold boundary representation based on partial topological entities. Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, Ann Arbor, MI, USA.","DOI":"10.1145\/376957.376976"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Brisson, E. (1989, January 5\u20137). Representing geometric structures in d dimensions: Topology and order. Proceedings of the Fifth Annual Symposium on Computational Geometry, Saarbruchen, Germany.","DOI":"10.1145\/73833.73858"},{"key":"ref_43","unstructured":"Brauer, W., Rozenberg, G., and Salomaa, A. (1987). Algorithms in Combinatorial Geometry. Monographs on Theoretical Computer Science, Springer."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/j.compenvurbsys.2006.03.003","article-title":"Simultaneous storage of primal and dual three-dimensional subdivisions","volume":"31","author":"Ledoux","year":"2007","journal-title":"Comput. Environ. Urban Syst."},{"key":"ref_45","first-page":"59","article-title":"Topological models for boundary representation: A comparison with n-dimensional generalized maps","volume":"23","author":"Lienhardt","year":"1991","journal-title":"Comput.-Aided Des."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Boguslawski, P. (2011). Modelling and Analysing 3D Building Interiors with the Dual Half-Edge Data Structure. [Ph.D. Thesis, University of Glamorgan].","DOI":"10.1016\/j.isprsjprs.2010.11.003"},{"key":"ref_47","unstructured":"Jiao, X., and Weill, J.-C. (2012, January 7\u201310). OpenVolumeMesh\u2014A Versatile Index-Based Data Structure for 3D Polytopal Complexes. Proceedings of the 21st International Meshing Roundtable, San Jose, CA, USA."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Brimkov, V.E., and Barneva, R.P. (2012). Modeling and Manipulating Cell Complexes in Two, Three and Higher Dimensions. Digital Geometry Algorithms, Springer.","DOI":"10.1007\/978-94-007-4174-4"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Kim, M.-S., and Shimada, K. (2006, January 26\u201328). Representing Topological Structures Using Cell-Chains. Proceedings of the Geometric Modeling and Processing\u2014GMP 2006, Pittsburgh, PA, USA.","DOI":"10.1007\/11802914"},{"key":"ref_50","unstructured":"Fradin, D., Meneveaux, D., and Lienhardt, P. (2002). Sample Space and Hierarchy of Generalized Maps: Application to Architectural Complexes, AFIG\u2014French Association of Computer Graphics."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Silva, F.G.M., and Gomes, A.J.P. (2003, January 11\u201314). Adjacency and incidence framework: A data structure for efficient and fast management of multiresolution meshes. Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia, Melbourne, Australia.","DOI":"10.1145\/604471.604503"},{"key":"ref_52","first-page":"19","article-title":"Binary spatial operations on cell complex using incidence graph implemented at a spatial database system Hawk Eye","volume":"3","author":"Kunihiko","year":"2006","journal-title":"Prog. Inform."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/282918.282923","article-title":"Primitives for the manipulation of general subdivisions and the computation of Voronoi","volume":"4","author":"Guibas","year":"1985","journal-title":"ACM Trans. Graph."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.cad.2008.11.006","article-title":"Consistency constraints and 3D building reconstruction","volume":"41","author":"Horna","year":"2009","journal-title":"Comput.-Aided Des."},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.1467-9671.2006.00251.x","article-title":"Requirements for Topology in 3D GIS","volume":"10","author":"Ellul","year":"2006","journal-title":"Trans. GIS"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/3\/102\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:35:01Z","timestamp":1760186101000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/3\/102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,27]]},"references-count":55,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,3]]}},"alternative-id":["ijgi8030102"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8030102","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,27]]}}}