Een verdeel-en-heers aanp
een vario-schaal structuur
Zo'n vijf jaar geleden is in Geo-
Info het concept van vario-schaal
geo-informatie beschreven
(Van Oosterom en Meijers, 2012).
In dit eerdere artikel werd de eerste
echt geleidelijke vario-schaal
structuur gepresenteerd: een delta
schaal geeft een delta in de kaart
(en hoe kleiner de delta schaal hoe
kleiner de delta kaart). De afgelopen
vijf jaar is er veel R&D verricht om
het concept van vario-schaal geo-
informatie te realiseren: ontwikkelen
van prototypen en testen met
echte data. In het kader van het
Open Technologieprogramma
(OTP van STW, Stichting Technische
Wetenschappen) project 11185
'Vario-scale geo-information' is er de
afgelopen jaren veel vooruitgang
geboekt. De belangrijkste resultaten
zullen in een serie beknopte
artikelen worden behandeld. Dit is
het derde artikel in de serie.
14
Geo-Info I 2017-3
Door Radan Saba, Martijn Meijers en
Peter van Oosterom
Grote datasets met geografische gegevens in
vector formaat met een verdeel-en-heers strate
gie verwerken, is niet eenvoudig. Dit geldt zeker
voor het probleem van kaartgeneralisatie, waar
(relaties tussen) nabije objecten in ogenschouw
moeten worden genomen. Om een vario-schaal
structuur af te leiden, waarbij de originele set
aan kaartobjecten te groot is om in één keer
in het hoofdgeheugen van een computer te
laden, is het nodig de input in kleinere blokken
op te delen. Daarvoor hebben we een verdeel-
en-heers aanpak ontwikkeld, zodat we -
onafhankelijk van de grootte van de input - de
hele dataset toch om kunnen zetten naar een
vario-schaal structuur (waarna deze gebruikt
kan worden, bijvoorbeeld in een client-server
architectuur, zie het tweede artikel in deze serie,
Huang, 2017 - Geo-Info nummer 2, 2017).
Om enorme datasets aan te kunnen, is het dus
nodig dat de input wordt opgesplitst in kleinere
blokken met data. Deze blokken noemen we
'velden'. Door de kaartobjecten op te delen met
behulp van deze velden, wordt de hoeveel
heid gegevens die voor elk veld verwerkt moet
worden, beperkt. Bijkomstigheid is dat de
velden onafhankelijk van elkaar en tevens ook
tegelijkertijd kunnen worden behandeld. Dit
sluit goed aan op de huidige techniek van mul-
tikernprocessoren, waardoor - in vergelijking
zonder verdeel-en-heers aanpak - significante
tijdswinst te behalen valt. Daartegenover staat
dat de kaartobjecten die aan/over de rand van
de velden liggen speciale aandacht vereisen.
Aan het ontwerp van de verdeel-en-heers
aanpak hebben we de volgende eisen gesteld:
De aanpak moet onafhankelijk werken van
het type kaart dat gegeneraliseerd moet
worden.
De velden (partitionering) moeten zonder
tussenkomst van een gebruiker automa
tisch gegenereerd kunnen worden.
Elk kaartobject moet slechts eenmalig
gegeneraliseerd worden.
De aanpak moet parallelle verwerking
mogelijk maken.
De gegevens in de resulterende vario-
schaal structuur moeten er gelijk of nage
noeg gelijk uitzien qua vulling, als wanneer
deze zonder verdeel-en-heers aanpak in
één keer worden verkregen.
We zullen nu eerst de aanpak in detail uitleg
gen, waarna we een aantal gedane experi
menten met resultaten zullen toelichten.
De verdeel-en-heers aanpak
Het hele proces om een grote vario-schaal
datastructuur gevuld te krijgen, bestaat uit
een aantal stappen:
1. het maken van een partitioneringsgrid met
velden op meerdere niveaus (Fieldtree) en
de input hierover verdelen,
2. de velden een voor een generaliseren,
3. de afronding.
1. Fieldtree maken en objecten verdelen
Om de planaire partitie met nodes, edges en
faces in kleinere blokken te verdelen, maken we
gebruik van de zogenaamde Fieldtree datastruc
tuur (Frank en Barrera, 1990). De Fieldtree is
ontwikkeld voor GIS-toepassingen. Figuur 1 toont
dat de velden op meerdere niveaus zijn georgani
seerd met steeds verschoven oorsprong voor een
niveau. Alle velden op één niveau vormen samen
een grid. De structuur wordt compleet vastge
legd door een ingegeven parameter die aangeeft
hoe groot de velden op het laagste niveau zijn en
de geografische omvang (extent) van de dataset
(zie Figuur 1(a)).
Wanneer de lay-out van de Fieldtree vastligt,
kunnen de objecten worden verdeeld over de
velden. Elk object uit de topologische structuur
van de planaire partitie (node, edge of face) wordt
toegewezen aan het kleinst mogelijke veld waar
het qua omvang in past. In het geval een object
groter is dan een veld op het laagste niveau (of
deels over de rand ligt), wordt dit object in een
veld op een hoger gelegen niveau geplaatst
en komt dit object pas later aan de beurt in
het generalisatie proces. Door de verschoven
grids lukt dit altijd (omdat de grid lijnen steeds
verschuiven).
Zodra alle objecten toegewezen zijn aan een
veld, kan elk laagstgelegen veld worden gegene
raliseerd. Het generalisatieproces kan onafhanke
lijk per veld en tegelijk met andere velden worden
uitgevoerd. Merk op dat de vlakken (faces) alleen
worden gegeneraliseerd als ze compleet binnen
een veld liggen (en hier dus ook alle gerelateerde
nodes en edges bij aanwezig zijn). Als een
vlakobject over de rand heen ligt, komt dit vlak
