Het algoritme: SplitArea
keuze uit 2
verbindingen
type 0 type 1
type 3
type 2
Skelet segment
Geconstrainde edge
(originele vlakgrens)
Figuur 2 - Er kunnen 4 typen driehoeken worden
onderscheiden, door te kijken hoeveel zijdes van
een driehoek een originele vlakgrens vormen
(dikke lijnen). Door vervolgens de middelpunten
van de ongeconstrainde zijdes te verbinden, kun
nen we een set aan skeletsegmenten verkrijgen
(gestippelde lijnen).
te splitsen object er uit moet zien, maken
we gebruik van een zogenaamde attrac-
tiewaarde. Het ideale oppervlak wat een
buur vervolgens moet verkrijgen, moet in
verhouding staan met de attractiewaarde
van een specifieke buur ten opzichte van
de som van de attractiewaarden van alle
buren, die meedoen in de splitsoperatie.
Het gebruik van de attractiewaardes
betekent dus het verdelen van een vlak
over de buren op een gewogen manier:
hiermee moet het mogelijk zijn een
vlak niet alleen precies in het midden te
splitsen, maar ook om grotere delen aan
bepaalde, aantrekkelijkere buren toe te
kennen. Vooraf kunnen we aan de hand
van de attractiewaardes bepalen hoe de
verdeling er theoretisch uit moet zien en
achteraf kunnen we vaststellen in hoe
verre dit het geval is.
De invoer van het algoritme, wat we
SplitArea noemen, bestaat uit de grenzen
van het te splitsen vlak en de aanliggende
grenzen van de buurobjecten waarop
moet worden aangesloten (beide als
edges uit de topologische datastructuur).
De eerste stap is om een triangulatie uit
te voeren. Voor de triangulatie worden de
grenzen van het te splitsen object gebruikt.
Omdat er een Constrained Delaunay trian
gulatie gebruikt wordt, bevat de triangula
tie vervolgens alle grenzen van de invoer.
Op basis van de driehoeken die binnen het
te splitsen object liggen, kunnen we een
lijnrepresentatie van het vlakobject opbou
wen, dat we hier skelet zullen noemen.
Hiervoor gebruiken we een reeds bestaande
techniek (Uitermark et al., 1999; Ai and van
Oosterom, 2002): Door de driehoeken te
classificeren op basis van de hoeveelheid
zijdes die een originele vlakgrens van het
te splitsen object vormen en deze per cate
gorie op een vaste manier te behandelen,
verkrijgen we het skelet. We onderscheiden
4 typen driehoeken: o-driehoeken, i-drie-
hoeken, 2-driehoeken en 3-driehoeken
(afhankelijk van het aantal constrained
edges die onderdeel zijn van een driehoek).
Figuur 2 illustreert hoe skeletsegmenten
worden gemaakt op basis van het type van
de geclassificeerde driehoeken. Alle seg
menten samen vormen zo het uiteindelijke
skelet (Figuur 3a). Om het definitieve
skelet te verkrijgen, zullen we nog moeten
zorgen dat het skelet verbonden is met de
al bestaande vlakgrenzen van de buren
rond het object dat we willen splitsen, zie
Figuur 3b. Elke aangelegen buurgrens raakt
de rand van het object wat gesplitst wordt
in één of twee knopen (nodes). Als zo'n
knoop nog niet verbonden is met het skelet,
wordt er een verbindingssegment gemaakt
langs een bestaande zijde van een driehoek.
Afhankelijk van hoe de triangulatie
eruitziet, kunnen er vervolgens meer of
minder verbindingssegmenten per knoop
gegenereerd worden.
Indien er meer dan één verbindings
segment gemaakt wordt, is het nodig om
uit de set aan verbindingen er eentje te
kiezen. In onze implementatie hebben we
gekozen voor het langste segment, maar
andere keuzes zijn wellicht beter: de kort
ste, of de verbinding die het beste past bij
de richting van de aanliggende grens.
De volgende stap in het algoritme is om de
gegenereerde skeletsegmenten te voorzien
van de juiste links en rechts verwijzingen
(vanuit de originele topologische datastruc
tuur). Figuur 4 geeft een voorbeeld. Voor dit
doel bouwen we een tijdelijke graafstruc-
tuur op, waarin alle skeletsegmenten,
gekozen verbindingssegmenten en
aanliggende vlakgrenzen worden opge
nomen. Deze graaf representeren we met
een winged edge data structuur (Baumgart,
1975)- Het propageren van de topologische
relaties start op een willekeurige aanlig
gende grens. Hiervan wordt de vlakreferen-
tie gebruikt, totdat een andere aanliggende
vlakgrens wordt bezocht. Dan wordt hier
van de vlakreferentie gebruikt en dit spel
herhaalt zich, totdat alle skeletsegmenten
type 0
type 1
type 2
Figuur3a - Skeletsegmenten, die afhankelijk van het type driehoek
gegenereerd worden.
Figuur 3b - Verbindingssegmenten worden gerealiseerd als het skelet nog
niet verbonden is met deaanüggende vlakgrenzen. Merk op dat voor de
rechterknoop er een keuze is welke verbinding er uiteindelijk gekozen wordt.
Figuur 3 - Het skelet verkrijgen. De skeletsegmenten en verbindingen worden lokaal gecreëerd, dat wil zeggen voor elke driehoek afzonderlijk.
16 Geo-Info 2013-3
