Een gewone planaire vlakkenopdeling
van de ruimte wordt meestal opgesla
gen in een topologische datastructuur
met nodes (knopen), edges (randen)
en faces (topologisch vlak). Het pro
ces, hieronder beschreven, voor het
maken van een hiërarchische vlakken
opdeling gaat uit van een topologische
datastructuur [1] [2] [4] [6], De topo
logische elementen bezitten de volgen
de attributen en relaties (hiervoor zijn
verschillende implementaties denk
baar)
een node (of O-cel) bevat een punt en
een lijst van referenties naar inko
mende en uitgaande edges, gesor
teerd voor de desbetreffende hoek;
een edge (of 1 -cel) bevat een polylijn
(vorm), lengte, referenties naar de
linker en rechter faces, en referenties
naar de begin- en eindknopen;
een face (of 2-cel) bevat de opper
vlakte en een lijst van referenties
naar randen die de buitenring vor
men (een opeenvolging van randen
die een gesloten keten vormen) en
mogelijk binnenste ringen (gerela
teerd aan eilanden). Deze referenties
naar randen zijn elk van een of -
teken voorzien om de goede door
looprichting van een rand aan te
geven.
Deze topologische datastructuur bevat
enige redundante informatie, die een
efficiëntere verwerking in een later sta
dium mogelijk maakt. Nadat de topo
logische datastructuur is gemaakt, zal
in de volgende stappen een hiërarchi
sche vlakkenopdeling ontstaan, die in
de zogenaamde GAP-tree wordt opge
slagen (meer details in [10]):
1. voor elke face (vlakobject) a in de
topologische datastructuur wordt
er een voorlopige 'losse' knoop in
de GAP-tree gecreëerd en er wordt
een toevoeging aan de prioriteiten-
rij gedaan, gebaseerd op de Impor-
tantie(a)-waarde;
2. selecteer het minst belangrijke
vlakobject a. De prioriteitenrij on
dersteunt dit via de operatie 'de-
queue' om zo het vlakobject effi
ciënt op te zoeken;
3. gebruik de topologische datastruc
tuur om de buren van a te vinden
en bepaal voor elke buur b, de lijst
van samenvallende gemeenschap
pelijke randen en de totale lengte
hiervan Lengte (a,b)\
4. vul het gat in door buurman b met de hoogste functie-
waarde Samenvoeg(a,b) te zoeken. Meer details met be
trekking tot de stappen 3 en 4 worden in de volgende
paragraaf behandeld;
5. sla de polygoon en andere attributen van vlakobject a in
zijn knoop in de GAP-tree op en maak een tak in de
boom van ouderknoop b naar kindknoop a\
6. voeg face a toe aan face b, pas de topologische datastruc
tuur aan, herbereken de functiewaarde Importantie(b)
en pas de positie van vlakobject b in de prioriteitenrij
aan op basis van de nieuwe importantiewaarde.
L]
Herhaal de stappen 2-6 net zolang
totdat er slechts één enorm vlakobject
is overgebleven. Het resultaat is opge
slagen in de GAP-tree en het laatste
vlakobject vormt de wortel (root) van
de GAP-tree. Tijdens het interactieve
gebruik in een GIS zal deze van tevo
ren berekende GAP-tree worden afge
daald totdat de knopen (behorende bij
Fig. 2. vlakobjecten) onder het vereiste importantieniveau voor de
Nieuwe enclaves gewenste kaartrepresentatie dalen. Fig. 1 toont een frag-
kunnen ontstaan ment van een topografische kaart in de vorm van een vlak-
wanneerfaces kenpartitie met daarnaast de GAP-tree, berekend volgens
worden samen- de hierboven beschreven methode. Elke polygoon staat op
gevoegd. zichzelf en bevat alle coördinaten, en heeft dus geen lijst
met verwijzingen naar randen, zoals de faces die wel heb
ben. De GAP-tree is geen binaire boom, maar kan per ou
derknoop een willekeurig aantal kinderen hebben. Enkele
visuele resultaten van de on-the-fly generalisatie met echte
datasets zullen in het tweede artikel in het volgende num
mer worden getoond.
Implementatie
Nu wordt meer in detail beschreven op welke wijze de bes
te buur voor samenvoegen kan worden gevonden, inclusief
alle gemeenschappelijke randen met deze buur, en hoe de
topologische datastructuur moet worden aangepast na het
samengaan van twee vlakobjecten.
De minst belangrijke face wordt gevonden via de prioritei
tenrij in stap 2 en zal hier weer face a worden genoemd. De
begrenzing van een face wordt gerepresenteerd via een lijst
van verwijzingen naar randen die zowel de buiten- als de
eventuele binnenringen (ingesloten
enclaves) aangeven. Om een buur van
face a te vinden, moet men naar een
rand kijken en nagaan welke face er
aan de andere kant ligt. Wanneer alle
randen afgelopen zijn, zijn ook alle
buurfaces bekend. Het is mogelijk dat
een buur meerdere randen gemeen-
Fig. 3. schappelijk heeft (fig. 2). Het is belangrijk dat al deze ran-
Faceamet den worden opgespoord nog voordat de Samenvoeg(a,b)
mogelijke buren functiewaarde wordt berekend, omdat deze is gebaseeerd
b en c. op de totale lengte van de gemeenschappelijke grens.
445
GEODESIA
2000-I0
1
Hoe de beste buur te vinden (stappen 3 en 4)
•-
t IC-
