Fig. 4.
Drie situaties met
van links naar
rechts: Gewone
buren (1), Toe
voegen van enclave
aan omhullende
(1), Toevoegen
omhullende aan
enclave (1).
Gedurende het sequentieel doorlopen van de randen bin
nen een ring wordt er een, initieel lege, lijst L bijgehouden
met daarin alle buurfaces in behandeling. Dat wil zeggen,
de buren waarvan misschien nog niet alle gemeenschappe
lijke randen zijn gevonden. Elke keer dat er een nieuwe
buur wordt gevonden, wordt deze aan het begin van de
lijst L toegevoegd. Ingeval dat buur b opnieuw wordt
gevonden (d.w.z. b stond al ergens in de lijst L), dan zijn
alle buren in lijst L die voor buur b staan, compleet ge
vonden. Deze kunnen dan worden verwerkt en van lijst L
worden afgevoerd. Op het moment dat alle randen van een
face zijn doorlopen en er nog steeds buren in de lijst staan,
kunnen deze ook worden verwerkt. Het verwerken houdt
in: het berekenen van de Samenvoeg(a,b) functiewaarde en
het bewaren van de buur met de hoogste functiewaarde tot
nu toe. Merk op dat de beschreven procedure zowel voor
de buitenring (face a is een normale buur of face a is een
enclave binnen face b) alsook voor de binnenring werkt
(face a omvat de enclave face b).
Hierboven werd gesteld dat, indien buur b opnieuw wordt
aangedaan, alle buren voor buur b in de lijst L kunnen wor
den verwerkt. Het zal nu bewezen worden dat van deze bu
ren alle gemeenschappelijke randen met face a inderdaad
zijn gevonden via een bewijs uit het ongerijmde. Neem het
tegenovergestelde aan, wat betekent dat er vóór buur b, een
buur c in lijst L voorkomt, waarvan nog niet alle gemeen
schappelijke randen gevonden zouden zijn. Hieruit volgt
dan weer dat face c gemeenschappelijke randen heeft tussen
en na de gemeenschappelijke randen die face b met face a
heeft (fig. 3). Deze situatie impliceert echter dat de faces b
en c elkaar kruisen, wat onmogelijk is in het geval van een
planaire topologie. Indien de dataset correct is, kan dit niet
voorkomen. Tegenspraak, einde bewijs.
Aanpassen topologische datastructuur (stap 6)
Deze paragraaf beschrijft hoe het minst belangrijke face a
wordt samengevoegd met zijn meest compatibele buur b.
Faces worden in de topologische structuur via een lijst van
verwijzingen naar randen voorgesteld. Om twee buurfaces
te vereningen, moeten de twee lijsten met verwijzingen
naar randen (randlijsten) worden ver
bonden, de gemeenschappelijke ran
den worden verwijderd en moeten
nieuwe enclaves die mogelijk ont
staan, worden ontdekt. Het hangt van
de situatie af welke randlijsten met el
kaar verbonden moeten worden. Er
kunnen drie verschillende situaties
mogelijk zijn, die in fig. 4 (eenvoudige
gevallen) en in fig. 5 (complexere ge
vallen) worden getoond. Deze ver
schillende situaties kunnen met be
hulp van een polygoon-in-polygoon
test (of punt-in-polygoon test met be
hulp van de centroïde) worden be
paald.
In de situatie 'normale buren' moeten
de randlijst van de buitenring van face
a en de randlijst van de buitenring van
face b worden samengevoegd. Dit wil
zeggen dat de gemeenschappelijke
Fig. 5.
Drie situaties met
van links naar
rechts: Gewone
buren (2), Toe
voegen enclave aan
omhullende (2),
Toevoegen om-
hidlende aan
enclave (2).
Fig. 6.
Verbinding van
randlijsten.
randen worden verwijderd en de over
gebleven delen van de randlijsten wor
den gekoppeld. In de situatie 'voeg en
clave aan omhullende toe' moeten de
randlijst van de buitenring van face a
en de randlijst van de betreffende bin
nenring van face b worden samenge
voegd. Het kan zijn dat hierdoor alle
verwijzingen naar randen vervallen
(fig. 4). In de situatie 'voeg omhullen
de aan enclave toe' moeten de randlijst
van de betreffende binnenring van
face a en de randlijst van de buitenring
van face b worden samengevoegd.
Merk op dat ook hier complete rand
lijsten kunnen wegvallen. De manier
waarop de overgebleven delen van de
randlijsten moeten worden samenge
voegd, is in alle gevallen hetzelfde. Een
gemeenschappelijke rand maakt deel
uit van beide randlijsten. De randen
vóór en na deze verwijderde gemeen
schappelijke randen moeten nu met
elkaar worden verbonden (fig. 6).
Het verbinden van randlijsten moet
bij alle verwijderde gemeenschappe-
446
GEODESIA
next
previous
next
previous
