Vinden van correspondenties
In deze paragraaf wordt een overzicht gegeven van de
methoden en „gereedschappen" die gebruikt worden om
correspondenties te traceren tussen de GBKN- en
TOPlOvector-gebouwrepresentaties. Eerst wordt de imple
mentatie van een kaartversnijdingsprogramma (MAP-
OVER) beschreven en een programma voor de reconstruc
tie van de topologie (TOPOL). Deze programma's zijn het
basisgereedschap voor het vinden van correspondenties.
De oorspronkelijke gegevens, alsmede de resultaten van
MAPOVER en TOPOL, worden gevisualiseerd met de
GEO++-browser [9]. Hoe de (1-op-l, n-op-1, enz.)-corres-
pondenties uiteindelijk worden bepaald met behulp van
SQL-queries, wordt vervolgens uit de doeken gedaan.
Het kaartversnijdingsprogramma (MAPOVER) is geba
seerd op de R-Tree Ruimtelijke Index [10], omdat een be
langrijke operatie binnen het programma het ruimtelijk
zoeken is naar elkaar snijdende lijnstukken. Door gebruik
te maken van een R-Tree kan dit zeer efficiënt worden
gedaan. Eerst bouwt het programma een R-Tree met de
lijnstukken van de eerste kaart (de GBKN). Daarna wor
den de lijnstukken van de tweede kaart (de TOPlOvector)
toegevoegd in de R-Tree op de navolgende wijze:
als een lijnstuk géén ander lijnstuk doorsnijdt, kan het
eenvoudig in de R-Tree worden toegevoegd;
als een lijnstuk een ander lijnstuk doorsnijdt, dan:
a. wordt het andere lijnstuk verwijderd uit de R-Tree;
b. worden de twee lijnstukken gesplitst op het snijpunt, Fig. 2.
wat resulteert in het ontstaan van drie of vier lijn- Overlappende
stukken; gebouwen.
c. worden de nieuwe lijnstukken in de R-Tree „voor
zichtig" toegevoegd, dat wil zeggen ze kunnen wel
licht nog andere lijnstukken snijden, waarvoor de
zelfde procedure moet worden herhaald.
Merk op dat behoedzaamheid geboden is in speciale geval
len, bijvoorbeeld bij lijnstukken die elkaar (gedeeltelijk)
overlappen en eindpunten die elkaar raken (meer details
kunnen hierover worden gevonden in [11]). Na deze stap
pen te hebben uitgevoerd voor alle lijnstukken, is het kaart-
versnijdingsproces beëindigd en moet de topologie op
nieuw worden opgebouwd. Het reconstrueren van de topo
logie houdt in het maken van vlakken, uitgaande van de
lijnketens. TOPOL is het programma dat voor dit doel
wordt gebruikt [12]. De volledige begrenzing van een vlak
bestaat uit een reèks lijnketens. De begrenzing van een vlak
is te vinden door aan elkaar grenzende lijnketens één voor
één af te lopen, totdat men opnieuw de kant van de lijn-
keten vindt waarmee men begonnen is. De basis voor de
werking van zo'n algoritme is een datastructuur met lijn
ketens en knopen. In deze datastructuur heeft een lijnketen
een richting en verwijzingen naar begin- en eindknoop van
de lijnketen. Een knoop heeft een lijst van verwijzingen
naar zijn inkomende en uitgaande lijnketens, gesorteerd
naar absolute richting. Het proces van het rondlopen van
de begrenzing eindigt als iedere lijnketen twee keer is aan
gedaan: één keer aan de linkerkant en één keer aan de rech-
112
terkant. Speciale gevallen zijn eiland-
vlakken, die ontdekt kunnen worden
vanwege hun „negatieve" oppervlakte.
Eilanden worden gekoppeld in de
topologische datastructuur aan hun
ondervlak. Het vinden van het ouder-
vlak is ook gebaseerd op het ruimtelijk
zoeken met behulp van de R-Tree, in
combinatie met een punt-in-polygoon-
test. TOPOL levert alle lijnketens zo
danig op dat alle lijnketens links-
rechts-verwijzingen naar de vlakken
hebben (topologie). Deze informatie
wordt opgeslagen in de tabellen van
een relationele database, aangevuld
met „handige" informatie over de
vlakken, bijvoorbeeld een omhullende
rechthoek (bounding box). Tevens
wordt binnen elk vlak een punt dat
binnen dat vlak ligt, berekend (cen-
troïde).
G 437
F193
Als gebouwrepresentaties van de
GBKN en TOPlOvector corresponde
ren, vertonen zij een bepaalde mate
van overlap. Hiervan wordt gebruik
gemaakt om correspondenties op te
sporen. Stel dat gebouwen in de data
base een identificatienummer „bid"
hebben en dat de geometrie van een
gebouw wordt voorgesteld door „geo
metry" van het type „polygon". Alle
overlappende gebouwen van de twee
kaarten kunnen dan worden gevonden
met de „overlaps"-operator in de vol
gende SQL-query (in CA Openlngres
2.0 met OME/SOL) [13]:
select gbkn.bid, toplO.bid
from gbkn, toplO
where gbkn.geometry overlaps
top10.geometry
Het resultaat van deze query bevat alle
overlappende gebouwen van de twee
1998-3
GEODESIA
Kaartversnijdingsprogramma (MAPOVER)
Vinden van correspondenties
via SQL-queries
