publikaties
SAMENSTELLING NGL RAYONCOMMISSIES PER 1 JANUARI 1990
VTAK
VVL
VMDR
NVG
Groningen Friesland Drenthe
F. O. de Zeeuw
Van Meijerstraat 20
9061 CW Giekerk
ing. A. Kabel
Wagnerlaan 13
9402 SG Assen
B. J. H. Arke
Vledderinge 11
9402 HV Assen
ir. G. M. v.d. Slikke
Amelterhout 146
9403 EK Assen
Overijssel
ing. T. S. Haan
Wittemerslag 12
8131 WK Wijhe
ing. W. D. Top
Boerendanserdijk 14
8024 AH Zwolle
H. Kraayeveld
Meppelerdiep 96
8032 TE Zwolle
ir. J. v. Buren
Magistratenveld 620
7327 LK Apeldoorn
Gelderland
J. M. Herlaar
Drielse Rijndijk 45
6665 LP Driel
ing. W. Heemskerk
Hogenkampseweg 124
6871 JT Renkum
A. Stienstra
Retiefstraat 219
3851 AG Ermelo
ir. J. v. Buren
Magistratenveld 620
7327 LK Apeldoorn
Utrecht
ing. A. L. Feith
Wilgenhof 15
4128 SH Lexmond
ir. J. Erkelens
M. Maeterlinckweg 4
3731 CJ De Bilt
J. L. v. Beers
Mr. J. C. Buhrmannlaan 58
1381 GM Weesp
mr. ir. J. C. Anneveld
Mozartkade 3
2102 XM Heemstede
Noord-Holland
G. J. S. Castricum
Ardennenlaan 26
1966 RV Heemskerk
ing. A. J. v.d. Meer
Reigersbos 142
1107 ES Amsterdam
ing. J. Fokkink
Carneool 1
1703 AL Heerhugowaard
ir. C. Wiersma
Westerweg 47
1815 DC Alkmaar
Zuid-Holland
H. W. M. S. Bremmers
Tulpentuin 359
2272 EJ Voorburg
P. v. Schelt
Oudelandstraat 160
2691 CH 's-Gravenzande
C. W. G. D. M. Aarts
Magalhaeslaan 26
2803 XA Gouda
ir. R. M. Kathmann
Isabellaland 1416
2591 EE Den Haag
Zeeland
L. C. Vercouteren
Braamhof 2
4371 CK Koudekerke
D. v.d. Steenhoven
Oranjepad 12
4461 TP Goes
A. C. M. Sonke
Eendvogelstraat 63
4451 DR Heinkenszand
ir. N. G. H. Koopman
Hoofdstraat 40
4844 CE Terheijden
Noord-Brabant Limburg
vacature
ing. P. W. v. Aken
Hulstbosakker 29
5625 VR Eindhoven
ing. A. C. Zijderveld
W. Alexanderpark 15
5684 GN Best
ir. H. A. Hettema
Bosstraat 16
6099 AM Beegden
THE DESIGN AND ANALYSIS OF SPATIAL DATA STRUCTURES
APPLICATIONS OF SPATIAL DATA STRUCTURES
beide geschreven door H. Samet, uitgegeven door Addison-Wesley
Publishing Company, Inc. 1990, respectievelijk ISBN 0-201-50255-0,
493 pag. en ISBN 0-201-50300-X, 507pag., gebonden. Prijs per boek
f 120,—.
Met de snelle toename van ruimtelijke gegevens in digitale vorm,
zowel in de hoedanigheid van beelden als geografische informatie
systemen (GIS), worden ook vragen urgent als: hoe dienen deze
gegevens te worden gestructureerd en welke algoritmen zijn nodig
om het gewenste type informatie zo efficiënt mogelijk aan de ge
gevens te ontlenen.
Dat de problematiek rond zulk soort vragen allerminst triviaal is,
moge blijken uit de 900 pagina's die Samet in zijn beide, onlangs ver
schenen, boeken: The Design and Analysis of Spatial Data Struc
tures (in het vervolg boek I te noemen) en Applications of Spatial
Data Structures (in het vervolg boek II te noemen) nodig heeft om
slechts enkele facetten van de totale problematiek te belichten als
ook uit de meer dan 800 titels waaraan hij refereert.
Ruimtelijke gegevens hebben naast een thematische (of seman
tische) ook een geometrische dan wel topologische component: de
gegevens zijn gelokaliseerd in twee, drie of nog hoger gedimensio-
naliseerde ruimte. Zulks doet zich onder andere voor bij de computer
graphics, de GISsen, de beeldverwerking en de patroonherkenning.
Beide boeken bespreek ik vanuit de laatste twee optieken. Daaruit
zijn de boeken ook ontstaan.
Ruimtelijke gegevens kunnen vectorgestructureerd of rastergestruc-
NGT GEODESIA 90 - 1
tureerd zijn. Samet beperkt zich tot de rasterstructuur in hiërar
chische vorm, met name de quadtree en zijn driedimensionale equi
valent de octree. De quadtree is gebaseerd op recursieve decompo
sitie en is een verfijning van de matrixrepresentatie van raster-
gegevens met het doel om te besparen op geheugenruimte door
gebruik te maken van homogeniteit in de gegevens. In tegenstelling
tot de pyramide, waarbij de schaal van het raster telkens wordt
gehalveerd door samenvoeging van 2x2 elementen, is de quadtree
een representatie met een variabele resolutie.
In hoofdstuk 1 volgt, na een korte bespreking van een aantal basis
begrippen van rasterdata, zoals adjacency, een overzicht van quad
trees en octrees. De quadtree is onafhankelijk in meerdere discipli
nes ontstaan. Kennelijk is het een „natuurlijke" gegevensstructuur
voor rasterdata. De meest gebruikte quadtree berust op het succes
sievelijk opsplitsen van een raster in vier gelijke kwadranten. Zijn de
elementen in het kwadrant heterogeen, dan wordt verder gesplitst.
Dit proces herhaalt zich tot elk kwadrant uitsluitend elementen van
dezelfde soort bevat. Voor een binair raster zijn dit nullen en enen.
De benodigde geheugenruimte is volledig afhankelijk van de mate
van detail (aanwezigheid van hoge frequenties) in het raster. Het
schaakbordpatroon, waarbij de elementen om en om de waarde 0 en
1 hebben, is het ergste geval. De quadtree is niet verschuivings-
invariant; twee identieke beelden die alleen ten opzichte van elkaar
zijn verschoven, leiden tot heel verschillende quadtrees. Dit is een
belangrijk nadeel.
De basiselementen van de ruimtelijke gegevensstructuur worden
gevormd door punten, vlakken en lijnen. Bij 3-D gegevens komt daar
nog volume bij. Volume, te representeren met octrees, is onder
andere van belang bij solid modelling. Aan elk basiselement wordt
in boek I telkens één hoofdstuk gewijd, respectievelijk 2, 3, 4 en 5.
De inhoud richt zich vooral op het ontwikkelen van algoritmen om
vanuit de gegeven basiselementen te komen tot verschillende typen
25
