Computer-Aided Civil and Infrastructure Engineering · 2013 · 61 citations · 23 references
ComputingComputer ScienceGeoinformaticsGeographic Information SystemsGeomaticsGeometry3D Geographic Information SystemsGeographic Data StructuresGeometric Data StructuresSolid ModelingSpatial Data StructuresSpatial Relations3D TopologyGeographic Information RepresentationGeometric Data TypesGeometric Validity CheckingPolyhedron TheoryReference Data SetsSolid Geometry ModelingSolid Validation
International standards for geographic information define geometric primitives, and while 2‑D validation algorithms are widely used, the equivalent 3‑D solid definitions are largely ignored, leading to non‑compliant, problematic data exchange. I present a methodology to validate solids according to the international standards. The method is hierarchical, validating primitives of all dimensionalities and employs Nef polyhedra to analyze topological relationships among solid shells. A prototype implementation demonstrates the method’s feasibility, detailing key engineering choices and its application to real‑world 3‑D datasets.
Abstract The international standards for geographic information provide unambiguous definitions of geometric primitives, with the aim of fostering exchange and interoperability in the geographical information system (GIS) community. In two dimensions, the standards are well accepted and there are algorithms (and implementations of these) to validate primitives, that is given a polygon, they ensure that it respects the standardized definition (and if it does not a reason is given to the user). However, although there exists an equivalent definition in three dimensions (for solids), it is ignored by most researchers and by software vendors. Several different definitions are indeed used, and none is compliant with the standards: for example solids are often defined as two‐manifold objects only, although in fact they can be nonmanifold objects. Exchanging and converting data sets from one format/platform to another is thus highly problematic. I present in this article a methodology to validate solids according to the international standards. It is hierarchical and permits us to validate the primitives of all dimensionalities. To understand and study the topological relationships between the different parts of a solid (the shells) the concept of Nef polyhedron is used. The methodology has been implemented in a prototype, and I report on the main engineering decisions that were made and on its use for the validation of real‐world three‐dimensional data sets.
23
Jean‐Daniel Boissonnat, Olivier Devillers, Sylvain Pion et al. · Computational Geometry · 2002 · 200 citations · Full text