heugen. Daarom zouden de geografische data moeten wor
den opgeslagen op een geïntegreerde manier zonder re
dundantie, en waar nodig, tevens ondersteund door een
speciale datastructuur.
Detailniveaus zijn zeer nauw gerelateerd aan kartografische
generalisatietechnieken. Het idee van on-the-fly kaartgene-
ralisatie [10] verschilt sterk van andere benaderingen, zoals
beschreven in [5]. De term batch-generalisatie wordt ge
bruikt voor het proces waarin een computer een input
dataset krijgt en een output dataset retourneert met gebruik
van algoritmen, regels, of constraints [3] zonder menselijke
tussenkomst. Dit in tegenstelling tot interactieve generali
satie waarin de gebruiker interactief met de computer
werkt en een scala aan generalisatie-algoritmen kan toepas
sen en beoordelen voor gegeven situaties binnen de dataset.
On-the-fly kaartgeneralisatie maakt geen tweede dataset,
omdat dit redundante informatie zou opleveren. Het pro
beert een tijdelijke generalisatie te maken, alleen bedoeld
om vluchtig op het scherm getoond te worden, op basis van
een gedetailleerde geografische database. Snelle antwoor
den, gevraagd door de interactieve gebruikers van een GIS,
vereisen de toepassing van specifieke datastructuren, omdat
anders de generalisatie te traag zou gaan voor datasets van
enige omvang. Naast kaartgeneralisatie moeten deze data
structuren ook ruimtelijke selectie bieden, dat wil zeggen,
het moet mogelijk zijn alle objecten binnen een specifiek
gebied op efficiënte wijze te zoeken. Dit type datastructu
ren wordt 'reactive data structures' genoemd [7] [8] [9].
De GAP-tree, een reactieve datastructuur geschikt voor een
vlakkenpartitie, wordt hierna kort beschreven en is geba
seerd op [10]. De implementatie van de GAP-tree wordt
daarna in dit artikel behandeld. In het tweede artikel zal
vervolgens worden gekeken naar de testresutaten, waarin de
implementatie wordt geëvalueerd met behulp van twee
datasets: vlakGBKN en ToplOvector. Een aantal verbete
ringen voor de GAP-tree worden in dit tweede artikel aan
gegeven. Tenslotte worden de conclusies besproken, samen
met verwijzingen naar toekomstig werk.
De GAP-tree
Een vlakkenpartitie van de ruimte waarin elk punt in het
2D-domein tot precies één van de gebieden behoort, wordt
vaak gebruikt als basisstructuur van de kaart, bijvoorbeeld
topografische kaart, bodemkaart, kadastrale kaart en
thematische choropleethkaart. Enkele problemen die ont
staan tijdens het toepassen van generalisatietechnieken zijn
dan:
simplificatie. Onafhankelijke lijngeneralisatie kan resulte
ren in lelijke kaarten omdat de vlakobjecten overlappin
gen en/of gaten kunnen bevatten. Een oplossing voor dit
probleem is om een topologische datastructuur te gebrui
ken en lijngeneralisatie toe te passen op de gewone gren
zen en randen (en niet direct op de vlakken zelf);
selectie. Een onbelangrijk vlakobject weglaten zal een
kaart produceren met een gat {gap) wat natuurlijk onac
ceptabel is. Tot voor de GAP-tree bestond nog geen dui
delijke oplossing voor dit probleem.
Een gat dat ontstaat door het minst
belangrijke vlakobject weg te laten,
moet opnieuw worden ingevuld. De
beste resultaten zullen worden verkre
gen door het gat met buurvlakken in
te vullen. Dit kan vrij eenvoudig wan
neer het gat een enclave of 'eiland'
vormde in de topologische structuur;
het kan worden opgevuld met het om
liggende gebied. Bij 'niet-enclave' si
tuaties zal een goede keuze een stuk
moeilijker zijn.
Fig. 1.
Fragment van een
topografische kaart
met bijbehorende
GAP-tree.
Het minst belangrijke vlakobject a
heeft de laagste waarde voor de Impor
tantie functie, bijvoorbeeld:
Importantie (a) prioriteit_t (a)
Gebied (a)
waar prioriteit_t(a) de gewichtsfactor
is voor de objectklassen (typen) waar
toe vlakobject a behoort en Gebied(a)
de oppervlakte is van vlakobject a.
Buurman b met de hoogste waarde
voor de Samenvoeg(a.b) functie mag
het gat van vlakobject a invullen. Een
voorbeeld Samenvoeg(a,b) functie is:
Samenvoeg(a,b)
compatibiliteit_t(a,b)
Lengte (a,b)
met compatibiliteit_t(a,b), de compa
tibiliteit tussen de objectklassen (ty
pen) waartoe respectievelijk de vlakob
jecten a en b behoren, en Lengte(a,b)
de lengte van de gemeenschappelijke
grens tussen a en b. De compatibiliteit
is gerelateerd aan de semantische na
bijheid van twee objectklassen in de
objectclassificatie hiërarchie, die is ge
associeerd met de betreffende dataset.
Rekening houdend met de ruimtelijke
relaties, de importantie van objecten
en de compatibiliteit tussen objecten,
wordt een hiërarchische vlakkenopde-
ling gecreëerd.
444
ke
GEODESIA
forest cornfield town
cornfield
The scene The GAP-tree
la
island