Activities per year
Abstract
In GIS, the use of efficient spatial data structures is becoming increasingly important, especially when dealing with multidimensional data. The existing solutions are not always efficient when dealing with big datasets, and therefore, research on new data structures is needed. In this chapter, we propose a very general data structure for storing any real or abstract cell complex in a minimal way in the sense of memory space utilization. The originality and quality of this novel data structure is to be the most compact data structure for storing the geometric topology of any geometric object, or more generally, the topology of any topological space. For this purpose, we generalize an existing data structure from 2D to 3D and design a new 3D data structure that realizes the synthesis between an existing 3D data structure (the Dual HalfEdge (See Footonote 1) data structure) and the generalized 3D QuadArc data structure, (See Footonote 2) and at the same time, improves the Dual HalfEdge towards a simpler and more effective representation of cell complexes through Brep structures. We generalize the idea of the QuadArc data structure from 2D to 3D, but instead of transforming a simple edge of the QuadEdge data structure to an arc with multiple points along it, we group together primal edges of the Dual HalfEdge that have the same dual HalfEdge vertex tags (volume tags) into one Dual HalfArc whose dual is the common Dual HalfEdge and primal faces corresponding to dual. This corresponds to grouping together straight line segment edges into arcs. This allows us to transform the Dual HalfEdge data structure into a 3D data structure for cell complexes with fewer Dual HalfEdges. Since the input/output operations are the most costly on any computer (even with solid state disks), this will result in a much more efficient data structure, where computation of topological relationships is much easier and efficient, like cell complex homologies (See Footonote 3) are easier to compute than their simplicial counterparts. This new data structure, thanks to its efficiency, could have a positive impact on applications that need near real time response, like mapping for natural disasters, emergency planning, evacuation, etc.
Original language  English 

Journal  Lecture notes in geoinformation and Cartography 
Pages (fromto)  103117 
Number of pages  18 
ISSN  18632246 
DOIs  
Publication status  Published  2014 
Fingerprint
Dive into the research topics of 'The Dual HalfArc data structure: towards the universal Brep data structure'. Together they form a unique fingerprint.Activities
 1 Visiting another research institution

Universiti Teknologi Malaysia
Francesc/François Antón Castro (Visiting researcher)
30 May 2013 → 29 Aug 2013Activity: Visiting an external institution › Visiting another research institution