Implementatie
Geconstrainde triangulatie
M ook voorkomt in de triangulatie.
Experiment met de
TU Delft-campus
driehoeken uit de CDT te selecteren en
deze, in het geval van de dakvlakken,
op de juiste extrusiehoogte te brengen.
Dan worden de muren gecreëerd door alle
geconstrainde edges uit de CDT te bezoe
ken en deze omhoog te trekken, waarbij
de configuratie van aan elkaar liggende
grondvlakken in het oog wordt gehouden.
In de vorige paragraaf hebben we laten
zien dat het verkrijgen van de geometrie
van de (verticale) muurvlakken complexer
is dan dat dit op het eerste gezicht lijkt
vanwege hoogteverschillen en de manier
waarop gebouwen aan elkaar grenzen.
Het algoritme verhelpt dit probleem
elegant door gebruik te maken van het
concept node-kolom. Op de plek van elke
node uit de triangulatie wordt een node-
kolom opgericht. De node-kolommen dra
gen er zorg voor dat de rechtopstaande
vlakken (de muren) topologisch consistent
zullen zijn (zie voor meer details het kader:
De node-kolommethode). Hiervoor biedt
de CDT-structuur eenvoudig toegang tot
alle relevante informatie. Het algoritme
levert uiteindelijk een set gebouwen en
een set topologisch consistente vlakken
in 3D als uitvoer. Een gebouw is hierbij
gedefinieerd als een container voor de
set van vlakken (die de begrenzing van
het gebouw voorstellen) en is dus een
polyhedron. Vlakken van aan elkaar
gelegen polyhedra worden niet gedupli
ceerd en een gebouw heeft simpelweg
referenties naar de bijbehorende vlakken.
Om in plaats van een 3D-stadsmodel een
2,75D-oppervlakterepresentatie van alle
objecten uit te voeren (bestaande uit het
terrein, de muren en de daken van de
gebouwen), volstaat het om de driehoe
ken tussen het terrein en de gebouwen,
en de driehoeken tussen aan elkaar
grenzende gebouwen te verwijderen
(met de geschetste methode zijn al deze
driehoeken eenvoudig aan te wijzen).
Onze implementatie leest een set aan
polygonen (grondvlakken) waaraan een
attribuut met de hoogte voor de extrusie
is toegekend. Omdat de input voor onze
procedure bestaat uit een set van poly
gonen, betekent dit dat elke polygoon
onafhankelijk in de dataset aanwezig is.
Een lijnsegment dat de grens vormt tussen
twee aan elkaar liggende polygonen komt
twee keer voor. In de praktijk komt het
hierbij vaak voor dat polygonen elkaar voor
een deel overlappen, of dat er overshoot-
of undershoot-problemen zijn door'snap-
ping'van lijnen bij objectvorming. Om een
topologisch consistente 2Ü-dataset als
uitgangspunt te krijgen, gebruiken we het
open source GIS-pakket GRASS. Overigens
zouden hiervoor ook andere GIS-pakketten
gebruikt kunnen worden.
Vervolgens wordt de CDT berekend
met behulp van de CGAL-bibliotheek.
De invoer voor de CDT-berekening is
de uitvoer van GRASS: de grenzen van
de grondvlakken (dit zijn de constraints
voor de triangulatie) plus per grondvlak
een punt dat gegarandeerd binnen de
grenzen van het grondvlak ligt. Voor
het gemak noemen we dit punt hier de
centroïde, ook al kan een echte centroïde
buiten de grenzen van een grondvlak
vallen. Aangezien de CDT-datastructuur
niet automatisch kennis bevat over de
polygonen, is het nodig om elke driehoek
in de CDT te markeren met het identifica
tieattribuut van het gebouw waar deze
driehoek bij hoort. Hiervoor gebruiken we
Met een set M van punten en rechte
iijnsegmenten daartussen in R2 is een
geconstrainde triangulatie van M een
triangulatie waarbij elk segment uit
Zoals getoond in fig. 4, wordt elk poly
goon opgeknipt in driehoeken en om de
kennis over de polygonen te behouden
wordt aan elke driehoek het identifi
cerende attribuut van de invoerpoly-
goon, in dit geval de kleur, toegekend.
Elke polygoon wordt zo gerepresenteerd
door een set van aan elkaar gelegen drie
hoeken. Ook gaten in polygonen kunnen
op deze manier worden gerepresenteerd.
Een gat is altijd verbonden aan de
buitenring van een polygoon door een
(ongeconstrainde) triangulatie edge.
als startpunt de centroïde van elk grond
vlak (verkregen met behulp van GRASS) en
lopen we in de triangulatie om aangren
zende driehoeken te bezoeken, totdat een
geconstrainde edge onze weg blokkeert.
Op deze manier wordt aan elke driehoek
de identificatie van het bijbehorende
grondvlak toegekend. De driehoeken, die
het universum vormen (de ruimte tussen
de grondvlakken), worden ook als zodanig
aangemerkt (fig. 4 toont dit proces).
Het ExTRUDE-algoritme is door ons in Python
geïmplementeerd. Omdat ons programma
een lijst van uniek geörienteerde vlakken en
referenties tussen de vlakken en de gebou
wen bijhoudt, is het eenvoudig om te komen
tot verschillende soorten uitvoer. Op dit
moment kan er worden uitgevoerd naar:
een CityGML-bestand;
een PLC-bestand, als invoer voor
tetrahedralisatie;
een lijst van vlakken en een lijst van
gebouwen die beide rechtstreeks in
een database opgeslagen kunnen
worden;
een 2,75Ü oppervlakterepresentatie
van het terrein en alle gebouwen.
Om onze aanpak te testen, hebben we een
experiment uitgevoerd met data van de
campus van de TU Delft. Voor dit gebied
van 2,3 km2 met 370 gebouwen werd de
Fig. 4. Het berekenen van de CDT op basis van een topologisch consistente 2D-dataset. Elke driehoek wordt
vervolgens gemarkeerd met het identificatieattribuut van het gebouw waar deze driehoek bij hoort.
10 Geo-lnfo 2009-12
