parkeerstroken afgebeeld. Geen van
deze objecten komt in de TOPlO-
vector voor. De mutaties in deze ob
jecten hebben ieder op zichzelf geen
invloed op de TOPlOvector maar
kunnen tezamen wel degelijk relevant
zijn om gepropageerd te worden naar
de TOP 1 Ovector.
Geometrische aspecten
van wegennetwerken
De methode om wegelementen in een
wegennetwerk te vinden is gebaseerd
op de triangulatie van het totale weg
vlak. Triangulatie wordt gebruikt om
de hartlijnen (skelet) van de wegen te
vinden. De knooppunten in het skelet
definiëren de lokaties van de krui-
singspunten en de zijden van de drie
hoek rond een knooppunt worden ge
bruikt om de wegkruisingsvlakken van
de wegsegmenten te scheiden. Het
constrained Delaunay triangulatie
(CDT) algoritme is hier toegepast
[10], Een CDT van een verzameling
van n punten, tezamen met een verza
meling van niet-snijdende lijnsegmen-
ten (tussen de gegeven punten), heeft
de eigenschap dat alle invoerpunten en
lijnsegmenten ook weer in de uitvoer
zitten en dat het geheel de unconstrai
ned Delaunay triangulatie (UDT) be
nadert. Dit betekent dat de omhullen
de cirkel van elke driehoek geen ander
punt bevat, tenzij dit aan de andere
kant van een invoerlijnsegment ligt. In
het geval van het wegennetwerk zijn er
Fig. 4.
Deze twee T-
kruisingsvlakken
resulteren in twee
wegkruisings
vlakken en vijf
wegvakken.
F tg 5.
Met driehoeken
belegd wegennet
werk.
Fig. 6.
Een ander wegen
netwerk.
geen losse punten in de invoer en bestaat de verzameling
van invoerlijnsegmeiiten uit de kanten van de weg.
Het gebruikte algorijme kost orde grootte 0(n log n) tijd,
wat asymptotisch optimaal is. Het algoritme is gebaseerd
op de principes van twee andere algoritmen. Het eerste al
goritme is het UDfj-algoritme van Lee and Schachter [6]
en het tweede is het! CDT-algoritme van Chew [1]. Meer
details van het algoritme en de implementatie ervan kun
nen worden gevonden in [10].
In het algemene geval van een CDT-algoritme is de invoer
een graaf G (V; E) waarin V een verzameling van n
knooppunten is (zosnel losse punten als de eindpunten van
lijnsegmenten) en E een verzameling lijnsegmenten is, de
zogenaamde G-zijdén. Twee verschillende soorten zijden
komen voor in de ifitvoer van een CDT: G-zijden, reeds
aanwezig in de invoer, en D-zijden toegevoegd door het al
goritme. Indien de graaf geen G-zijden heeft dan zijn de
CDT en de UDT identiek. Het algoritme gebruikt de ver-
deel-en-heers strategie.
De methode om het skelet van de
CDT af te leiden is gebaseerd op Wil
schut [15]. In de triangulatie kunnen
vier verschillende soorten driehoeken
voorkomen. Afhankelijk van het aan
tal G-zijden in de driehoek hebben de
ze de volgende namen: 0-, 1-, 2- en 3-
driehoek. Een 3-driehoek is een uit
zondering en komt alleen voor wan
neer er in de invoer een los, niet
verbonden, wegvlak van driehoekige
vorm zit. Een wegkruisingsvlak kan
gevonden worden via een driehoek die
alleen D-zijden heeft en geen enkele G-zijde, dat is dus een
O-driehoek; zie de Jichte driehoeken in de figuren 5 en 6.
Een T-kruisingsvlak is een enkele O-driehoek zonder buur
O-driehoeken. Een normale kruising (4-wegkruisingsvlak)
wordt gedefinieerd; door twee buur O-driehoeken; bijvoor
beeld in de wegkrujsingsvlakken middenonder in figuur 6.
Een n-wegkruisingsvlak wordt gedefinieerd door (n-2)
buur O-driehoeken.
De 1-driehoeken zjijn de bouwstenen van de verbindende
wegsegmenten; zie; de donkere driehoeken in figuren 5 en
6. Ten slotte, de 2-driehoeken definiëren de einden van het
wegennetwerk, de doodlopende wegen. Overigens kan ook
een kleine bult in de kant van een wegsegment leiden tot
een 2-driehoek en lean daarom worden gezien als een hele
korte doodlopendq weg; zie het wegsegment rechtsboven in
figuur 6. Een oplossing voor dit 'probleem' is om (virtueel)
de 2-driehoeken die kleiner zijn dan een bepaalde drempel
waarde en buur zijn van een O-driehoek te verwijderen. In
dergelijke gevalleri worden ook de originele O-driehoeken
virtuele 1-driehoeken, dat wil zeggen onderdelen van ver
bindende wegsegmenten. Verder kan het voorkomen dat
319
GEODESIA
1999-7/8
Constrained Delaunay triangulatie
Interpretatie van de driehoeken
van het wegennetwerk
