An algorithm for overlaying 3D features using a tetrahedral network
Arno van der Most · Research Repository (Delft University of Technology) · 2004
De ontwikkeling van 3D GIS heeft de laatste jaren langzaam maar zeker vooruitgang geboekt.Het zwaartepunt bij het onderzoek en de ontwikkeling van 3D GIS lag vooral bij de visualisatie aspecten van driedimensionale gegevens uit databases en in mindere mate bij de opslag van driedimensionale gegevens.Pas sinds kort verschuift de aandacht geleidelijk naar gebruikersinteractie en analyse binnen een 3D GIS.Er zijn al wat buffer en hoogteanalyse tools beschikbaar, maar er is nog bijna geen onderzoek gedaan naar een van de meest gebruikte tools in 2D GIS, de map overlay.Overlay algoritmes behoren tot de meer complexe algoritmes binnen GIS.Complexe datastructuren die zeer grote hoeveelheden geometrische en topologische gegevens beschrijven zijn onderhevig aan complexe queries.In deze thesis wordt een poging gedaan om orde te scheppen in deze complexiteit en een algoritme te beschrijven dat een overlay kan uitvoeren op driedimensionale gegevens met behulp van een tetrahedron netwerk.Het algoritme dat beschreven wordt in deze thesis voert geen overlay uit op maps, of kaartlagen zoals map overlay algoritmes dat doen.Het algoritme is object georiënteerd en voert derhalve een overlay uit op individuele features in plaats van maps.Hoewel het geen voorwaarde was voor het onderzoek is het wel van belang onderscheid te maken tussen deze twee verschillende benaderingen van de gegevens voor het doen van een overlay.Om verwarring te voorkomen wordt het algoritme dat hier wordt behandeld aangeduid met de term feature overlay algoritme.Het feit dat overlay algoritmes behoren tot de meer complexe algoritmes binnen GIS samen met de hogere complexiteit van driedimensionale algoritmes ten opzichte van tweedimensionale algoritmes maakt het noodzakelijk eerst het algoritme in twee dimensies te verkennen.Het algoritme was ontworpen in de volgende drie stappen: 1. Formuleer een algemeen 'container' feature overlay algoritme 2. Vul het container algoritme met tweedimensionale sub-algoritmes 3. Vertaal de tweedimensionale sub-algoritmes naar driedimensionale sub-algoritmes 5.2 Phase 1: pre-processing 5.3 Phase 2: inserting features 5.3.1 Processing edges 5.3.2Processing sections 5.4 Phase 3: re-assembling features 6. Conclusions and recommendations 6.1 Conclusions 6.2 Recommendations Glossary Refferences Appendix A: source code for 2D feature overlay algorithm 10 3. 2D feature overlay algorithmVisualising and describing three-dimensional processes in such a way that it's easily comprehensible and insightful for the reader is a difficult task.In order to make the explanation of the three-dimensional feature overlay algorithm easier to understand this chapter contains an detailed description of the same algorithm for two-dimensional features.Before continuing with the algorithm itself.Some important terms used during the discussion of the algorithm are elucidated in this section.After this, a general overview of the entire algorithm is given in section 3.2.This is done by globally describing the steps that are taken in the three main phases of the algorithm.Each of these phases, pre-processing, feature insertion, and post-processing, will then be described in more detail in the three following sections.