SplitArea
Een algoritme om vlakken te splitsen
voor de tGAP datastructuren
Artikel
Hoewel variabele schaal datastructuren een mogelijke oplossing zijn om geografische gegevens op
meerdere schalen consistent bij te houden en te ontsluiten (bijvoorbeeld via webservices), staat of valt een
dergelijke oplossing met een goed uitgevoerd generalisatieproces. Om op kleinere kaartschalen te kunnen
beschikken over lijnrepresentaties van langgerekte objecten (zoals wegen, rivieren, kanalen en spoorbanen,
kortom infrastructuur), presenteert dit artikel onderzoek naar het ontwerpen van een splitsoperatie die de
overgang van vlak- naar lijnobject faciliteert.
Martijn Meijers en Peter van Oosterom
De eerste ideeën voor een datastructuur,
die het mogelijk maakte om kaarten af
te leiden op een variabele kaartschaal,
waren gebaseerd op een simpele data
structuur met polygonen (van Oosterom,
1993; van Oosterom and Schenkelaars,
1995). Het belangrijkste doel was om een
representatie met variabele schaal te
hebben voor geografische datathema's,
die een vlakopdelend karakter hebben,
zoals topografische data, bodemkaarten
en landsgebruikskaarten. Op basis van
een input dataset wordt een hiërarchische
representatie opgebouwd, door gene
ralisatie operatoren zoals simplificatie,
selectie en eliminatie toe te passen.
Dit proces wordt gestuurd door twee
functies: belangrijkheid van objecten
(normaal berekend door de grootte van
een object en een toegekende belangrijk-
heidswaarde voor de klasse van het object
- hiermee kan in het generalisatie proces
gestuurd worden welke objecten bena
drukt moeten worden) en attractiviteit van
twee objectinstanties (typisch afgeleid
van de lengte van de gezamenlijke grens
en hoe compatibel de objectklassen
van de twee objecten zijn - de relatieve
belangrijkheid). Iteratief wordt nu elke
keer een object (het minst belangrijke)
verwijderd uit de vlakkenpartitie en het
vrijgekomen gebied wordt toegewezen
aan het meest aantrekkelijke buurobject.
Het resultaat is een boomstructuur van
polygonen (Engels: GAP-tree, Generalised
Area Partitioning tree), die vervolgens
gebruikt kan worden voor het selecteren
van een representatie op een specifieke
kaartschaal. Naast veelbelovende resulta
ten, zoals constante responstijd voor het
leveren van een kaartfragment op een wil
lekeurige kaartschaal, werden twee pro
blemen geconstateerd: 1. het versimpelen
van de geometrie van twee onafhankelijke
polygonen leidde tot gaten en overlap
en 2. de kartografische kwaliteit van de
kleinere kaartschalen is suboptimaal.
Om het eerste probleem te verhelpen, is
voorgesteld om een topologische aanpak
voor data opslag te volgen, in plaats van
eentje op basis van polygonen (Vermeij
et al., 2003; van Oosterom, 2005). In eerste
instantie bleek de topologische imple
mentatie te leiden tot een grote hoeveel
heid benodigde opslagcapaciteit door
redundante topologische verwijzingen (in
een test met grootschalige topografische
data van de gemeente Amsterdam werd
voor elke originele grens gemiddeld
17 keer een variant met net iets andere
topologische verwijzingen opgeslagen).
Extra onderzoek heeft geleid tot een meer
zuinige (en meer geavanceerde) opslag
structuur, waarbij de redundantie in de
verwijzingen wordt vermeden (Meijers et
al., 2009) en de benodigde hoeveelheid
opslagruimte maximaal twee keer de
grootte van de originele dataset is.
Om het tweede punt'kartografische kwa
liteit'te verbeteren, presenteert dit artikel
een splitsoperatie voor gebruik binnen
de topologische GAP (tGAP) datastruc
tuur. Hiermee is er nu de beschikking
over: 1. een versimpelingsoperatie voor
de vlakgrenzen, 2. is het mogelijk om een
vlak te splitsen over zijn buren, door een
(gewogen) splitsoperatie of 3. om selectie
en eliminatie toe te passen door een vlak
samen te voegen met zijn meest aantrek
kelijke buurman (voor een normaal vlak-
object). De splitsoperatie is handig voor
langgerekte infrastructurele objecten, die
op de grootste schaal nog als vlakobject
voorkomen, maar na de splitsoperatie
gerepresenteerd kunnen worden als een
lijnobject.
We beschrijven hoe het algoritme werkt,
geven details over welke randvoorwaar
den (optimalisatie doelstellingen) we voor
het algoritme bepaald hebben en hoe we
het resultaat van het algoritme automa
tisch beoordelen en of de kwaliteit van
splitsen wel voldoende is. Dit heeft geleid
tot een aantal aanpassingen aan de initi
ële oplossing en laat tevens beperkingen
van het geschetste algoritme zien.
14 Geo-lnfo 2013-3
