Generaliseren van vlakkenpartities (I)
GAP-trees, theorie en implementatie1)
Inleiding
GEODESIA
2000-I0
geo-information engineering, spatial data structures, theory
geo-informatievoorziening, ruimtelijke gegevensstructuren, theorie
KEYWORDS
TREFWOORDEN
Dit artikel toont de resultaten van on-the-fly generali
seren met behulp van de GAP-tree ('Generalized Area
Partitioning-tree oftewel de 'Gegeneraliseerde Vlakken
Partitie'-boom) toegepast op twee grootschalige topo
grafische datasets, de vlakGBKN 11.000 en de
ToplOvector. Door toepassing van de GAP-tree is het
nu mogelijk om interactief te navigeren door deze ruim
telijke datasets vanaf de oorspronkelijke schaal 11.000
(110.000) via een middenschaal als 125.000 tot en
met zelfs kleine schalen 1100.000).
Het blijkt dat met de opkomst van in-
ternet-GIS de behoefte aan on-the-fly
generaliseren sterk is toegenomen.
Ten eerste omdat de bandbreedte be
perkt is en het dus van belang is dat er
zo weinig mogelijk onnodige details
worden overgestuurd; dat scheelt im
mers tijd. Belangrijk is dat snel een
goed kaartbeeld wordt opgebouwd,
dat eventueel later kan worden aange
vuld met meer details, al dan niet na
het inzoomen op een specifieke loca
tie. Ten tweede maakt internet-GIS
het mogelijk om datasets van verschil
lende bronnen (en dus vaak ook van
verschillende schalen) te combineren,
maar dit is alleen zinnig indien eerst
van alle datasets een presentatie op ge
lijke schaal wordt afgeleid.
Behalve de testresultaten en de imple
mentatie van de standaard GAP-tree,
wordt er een uitbreiding beschreven,
die is gebaseerd op de toevoeging van
parallelle lijnen aan de GAP-tree voor
lineaire objecten zoals straten en wa
terwegen. Dit maakt het mogelijk om
een betere en duidelijkere, in de breed
te overdreven, representatie van deze
objecten op kleinere schalen te tonen.
drs. J. D. van Putten'), Nationaal
Lucht- en Ruimtevaartlaboratorium
te Marknesse, en
prof.dr.ir, P.J.M. van Oosterom,
TU Delft, afdeling Geodesie,
sectie GISt.
Gepresenteerd op het
Internationaal Sym
posium over Spatial
Data Handling,
SDH'98 Vancouver,
Canada, 12-15 juli
1998.
2) Dit onderzoek werd
uitgevoerd tijdens de
periode dat de auteur
bij het Kadaster mee
werkte aan dit pro
ject voor het behalen
van haar doctoraal-
Hoewel het gebruik van de GAP-tree zeer geschikt is voor
efficiënte on-the-fly generalisatie, vergt het in één slag
bouwen van de GAP-tree voor een grote dataset soms (te)
veel computergeheugen. Daarom wordt er een nieuwe
methode voorgesteld om van een grote dataset de GAP-tree
representatie te bouwen, gebaseerd op een verdeel-en-heers
techniek.
Dit artikel is opgesplitst in twee gedeelten. Dit eerste deel
behandelt de theorie en de implementatie van de GAP-tree,
terwijl het tweede gedeelte in het vol
gende nummer nader ingaat op de
testresultaten en de verbeteringen.
Met de komst van Geografische Infor
matie Systemen (GIS) is de wijze
waarop mensen kaarten of geografi
sche data gebruiken drastisch veran
derd. Moderne informatiesystemen
maken het mogelijk door geografische
datasets te navigeren door middel van
het selecteren van (typen van) objec
ten en ze vervolgens op verschillende
schalen af te beelden. Simpelweg ver
kleinen van objecten als de gebruiker
uitzoomt, resulteert echter in een ma
tige kwaliteit van de kaartrepresenta-
tie. Bovendien wordt deze kaartrepresentatie erg langzaam
opgebouwd, omdat deze veel te veel informatie bevat. Niet
alleen moeten de objecten worden verkleind, maar ze moe
ten ook veel minder gedetailleerd worden weergegeven
(vanwege de kleinere schaal). Minder belangrijke objecten
moeten in hun geheel worden weggelaten, omdat ze voor
de kleinschalige kaart niet van belang zijn. Een eenvoudige
oplossing voor dit probleem is om de kaartrepresentatie op
verschillende schalen, dus op verschillende detailniveaus,
op te slaan. Dit brengt enkele serieuze nadelen met zich
mee, zoals mogelijke inconsistenties tussen de verschillende
representaties en een fors toegenomen gebruik van het ge-
443
