klasse
label
^/"object
identificatie
Fig. 2. Verbinding van een objectidentificatie met een klasselabel
(object-klasse-link).
2.1. Geometrie van vectorkaarten
Een vector gestructureerde terreinbeschrijving zullen we
een „vectorkaart" noemen. Het woord kaart wordt hier
dus niet in de traditionele zin gebruikt. In een vectorkaart
worden terreinobjecten in geometrische zin beschreven
door de lineaire structuur van lijnobjecten, de grenzen
van vlakobjecten en de positie van puntobjecten. We
zullen nu proberen om fig. 1 verder uit te werken. Daarbij
is van belang welke elementaire gegevenstypen voor de
geometrische gegevens moeten worden ingevoerd, hoe
die onderling verbonden zijn en wat hun verbindingen zijn
met de objectidentificaties.
voorkomt. Als twee knooppunten beide in één keten voor
komen, zijn ze verbonden. Als ieder paar knooppunten in
een graaf is verbonden, is de graaf „verbonden". In
overige situaties is het een „niet-verbonden graaf".
Met deze definities kunnen we nu de verbondenheid van
een verzameling knooppunten en zijden onderzoeken,
dus de topologie van een graaf G die bestaat uit N en
A G (N, A).
Voorbeeld 1
G (N, A)
N {1, 2, 3, 4, 5, 6)
A j(1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (3, 4)}
i[x
4 3
(a) (b)
Fig. 3. Interpretaties van G (N, A).
2.1.1. Inschakeling van de grafentheorie
Een aantal auteurs heeft zich met dit probleem bezigge
houden en verschillende oplossingen zijn in de literatuur
te vinden [1, 2, 3, 9, 10, 11, 12, 15]. De verschillen komen
meestal voort uit het feit dat in eerste instantie wordt
gezocht naar een efficiënte of zelfs optimale gegevens
structuur. Wiskundige duidelijkheid of strengheid wordt
dan ondergeschikt gemaakt aan praktische overwegin
gen die binnen een bepaald toepassingsveld nodig zijn.
Daardoor ontstaan verschillen in de definitie van geome
trische primitieven en de wijze waarop deze aan object
identificaties of klassen worden verbonden. Als men de
verschillende benaderingen vergelijkt, wordt het duidelijk
dat de grafentheorie een consistente verzameling van
primitieven levert.
Een graaf is een collectie van twee verzamelingen:
een verzameling van knooppunten (nodes)
N
{n,n2,nh,nr}
een verzameling van zijden (arcs)
A ja,, a2,ara„|
waarbij voor iedere a, e A geldt a, jnp, nqj
met np, nq e N
Dus een zijde is een deelverzameling bestaande uit twee
elementen uit N. Als een knooppunt n, in m zijden voor
komt, is zijn orde o(n;) m. In het vervolg gaan we
ervan uit dat zijden geordende deelverzamelingen van
N zijn, dat wil zeggen dat de volgorde np en nq
in a (np, nqj van belang is.
Dus als a, (np, np) en
a: |nq, npj geldt aar
In dat geval spreekt men van gerichte zijden. In het ver
volg zullen we kortweg „zijde" in plaats van „gerichte zij
de" schrijven.
Als twee knooppunten in een zijde voorkomen, worden ze
„verbonden door die zijde". Als twee zijden een knoop
punt gemeenschappelijk hebben, zijn die zijden ver
bonden. Een serie van verbonden zijden zullen we een
„keten" noemen. In het vervolg zal deze term echter
alleen worden gebruikt voor een serie van verbonden
zijden, waarin iedere zijde slechts één keer voorkomt, ter
wijl ieder knooppunt slechts in maximaal twee zijden
Dit voorbeeld laat zien, dat een graaf nog geen volledige
beschrijving van een kaartgeometrie levert. De interpreta
tie in fig. 3a lijkt veel op een kaart. Fig. 3b is echter een
totaal andere, niet-geometrische, interpretatie van de
zelfde graaf. Dit betekent, dat voor de beschrijving van
een kaartgeometrie nog informatie moet worden toege
voegd. Voor een situatie in het platte vlak kan dit door de
toevoeging van positie-informatie in de vorm van een
(x, y)-coördinatenpaar per knooppunt (fig. 4).
Voorbeeld 2
G (N, A)
N j1(x„ y,), 2(x2, y2),6(x6, y6)j
A j(1, 2), (1, 3),(3, 4)}
(b)
Fig. 4. Interpretaties van G (N. A). na toevoeging van positie
informatie.
Door gebruik van de positie-informatie lijken deze twee
interpretaties veel op elkaar. Er is echter nog een ver
schil, doordat de zijden niet dezelfde vorm hebben. Vorm-
informatie moet nog worden toegevoegd om eenduidig
heid in de interpretaties van grafen te verkrijgen. Dit kan
op twee manieren:
in een parametrische vorm: de parameters definiëren
een wiskundige kromme;
door een keten van punten met coördinaten, waarbij
ieder paar opeenvolgende punten in de keten is ver
bonden door een rechte lijn.
Het gevolg van de tweede oplossing is, dat een tweede
soort van punten wordt toegevoegd naast de knooppun-
394
NGT GEODESIA 89 - 9
