lijke randen gebeuren, zowel bij de
knopen vóór als na deze verwijderde
rand. Tijdens dit proces van verbinden
ontstaan weer nieuwe randlijsten die
ringen vormen. Een nieuwe randlijst
kan worden gevonden nadat een ver
wijderde gemeenschappelijke rand is
verwerkt. De lijst met gemeenschap
pelijke randen EL kan voorwaarts of
achterwaarts doorlopen en worden af
gehandeld, maar de volgorde waarin
die gemeenschappelijke randen wor
den afgehandeld, mag niet verande
ren. In het geval dat een gemeenschap
pelijke rand e niet de eerste rand in de
lijst EL is, zoek dan een nieuwe rand
lijst aan de kant van de knoop van de
gemeenschappelijke rand e aan de kant
waar de andere gemeenschappelijke
randen al verwerkt zijn; bijvoorbeeld
knoop a van rand e2 in fig. 7, aanne
mende dat rand el als eerste is ver
werkt. Ingeval dat de gemeenschappe
lijke rand e de laatste rand in de lijst
EL is (bijvoorbeeld e3), moet ook een
nieuwe randlijst aan de andere kant
van deze gemeenschappelijke rand
worden gevonden.
Twee verschillende soorten randlijs
ten, die de nieuwe ringen van de sa
mengestelde face representeren, kun
nen nu zijn ontstaan. Dit zijn randlijs
ten met een draairichting met de klok
mee en randlijsten die tegen de klok
indraaien. Er zal precies één randlijst
ontstaan, die met de klok meedraait;
dit is de buitenring van de nieuwe
face. De overige randlijsten, indien
aanwezig, zullen alle tegen de klok in
draaien en komen overeen met de bin
nenringen van de nieuwe face.
Bij het samenvoegen van twee faces is
het mogelijk dat nieuwe 'loshangende'
randen ontstaan, die verwijderd moe
ten worden. Dat wil zeggen, twee opeenvolgende verwijzin
gen naar randen in de nieuw gecreëerde randlijst wijzen
naar dezelfde rand, maar wel met een tegenovergesteld te
ken. Dit zal zowel bij rand el als rand e2 in fig. 8 gebeuren.
Deze randen moeten worden ontdekt en verwijderd. Merk
op dat een nieuwe loshangende rand alleen kan ontstaan
indien de oorspronkelijke rand zowel links als rechts dezelf
de face had. Deze randen zijn niet nodig voor het werken
met enclaves in een planaire partitie, maar kunnen in de
dataset voorkomen om een lijnvormig object te represente
ren, bijvoorbeeld een hek. In plaats van het verwijderen van
deze randen bij het bouwen van de GAP-tree, hadden ze
ook vooraf verwijderd kunnen worden.
Fig. 7.
Creatie van
nieuwe
(binnen)ringen.
Afsluiting
Fig. 8.
Nieuwe los
hangende randen.
Deel twee van dit artikel gaat nader in op de resultaten van
het testen van de GAP-tree bij het gebruik van een
vlakGBKN en de ToplOvector. Ook zullen twee belang
rijke verbeteringen worden beschreven, namelijk parallelle
lijnen om lineaire objecten beter te kunnen meenemen in
het generalisatieproces, onder andere door deze te over
drijven, en een aanpassing om met zeer grote datasets om te
kunnen gaan.
Generalization of Area Partitions (part 1)
The GAP-tree is a structure which can store generalizations in
such a way thatfor every scale the matching generalization can
be determined rapidly. In this research GAP-trees were built
for two different datasets, the vectorGBKN and the ToplO
vector. After setting the feature type priority and compatibility
values, the generalizations were performed automatically. This
is of great importance for efficient use of cartographic data via
the internet. During webbrowsing, a correct generalization for
every maplevel is determined and can be shown very fast. In
this first part of the article the authors discuss the theoretical
backgrounds and the implementation. In the next issue of this
magazine the second part will deal with the test results and
discuss possible improvements.
[1] Boudriault, Gerard, Topology in the TIGER file.
Auto-Carto 8, p. 258-269, 1987.
[2] DGIWG. DIGEST - digital geographic information -
exchange standards - edition 1.1. Technical report,
Defence Mapping Agency, USA, Digital Geographic
Information Working Group, oktober 1992.
447
GEODESIA
Summary
Literatuur