-H
k-N
b^
bdR
btd-
-N
F
van een toevoeging of aanpassing van een object (dit is
mogelijk in de meeste DBMSen);
b. herschrijf de zoekopdrachten voor rechthoek-overlap
naar SLC-vragen (alleen mogelijk in geavanceerdere
DBMSen, maar altijd mogelijk binnen een CIS-inter
lace van het DBMS).
Een combinatie van de Field-tree en de Morton-code
(Quadtree) is gebruikt als basis voor de SLC. Deze structu
ren worden beschreven in het volgende hoofdstuk. In [2]
wordt een methode beschreven, gebaseerd op een combina
tie van de Quadtree en Morton-code. Het nadeel van deze
methode is dat een object, dat een hoofdgrens van de
Quadtree doorsnijdt, een waarde krijgt overeenkomstig het
hoofdgebied van de Quadtree. Later, tijdens het zoeken, zal Fig. 1.
dit kleine object altijd worden opgehaald wanneer het De Quadtree en
zoekgebied het hoofdgebied van de Quadtree overlapt, zelfs quadcodes.
wanneer dit kleine object er zelf ruim buiten valt. Dit pro
bleem kan worden verminderd door meer dan één waarde
per object toe te staan [3]. De nadelen van deze methode
zijn het toegenomen geheugengebruik en het feit dat de
zoekvoorwaarde ingewikkelder zal worden en daarom ook
langzamer. De SLC-methode kent deze nadelen niet. In de
volgende hoofdstukken worden de benchmark-resultaten
gepresenteerd.
Basisstructuren
In dit hoofdstuk zullen beknopte beschrijvingen worden
gegeven van de Region Quadtree, de Morton-waarde en de
Field-tree. Meer details kunnen worden gevonden via de
gegeven literatuurverwijzingen.
De Quadtree is een generieke naam voor allerlei zoek-
bomen die worden opgebouwd door de ruimte recursief in
vier quadranten op te splitsen. In [14] [15] wordt hiervan
een goed overzicht gegeven. De bekendste Quadtree is de
region Quadtree die wordt gebruikt om gerasterde benade
ringen van een polygoon op te slaan. Het domein wordt
eerst omsloten door een vierkant. Vervolgens wordt her
haaldelijk een vierkant in vier vierkanten van gelijke groot
te gesplitst, net zolang tot het geheel binnen (een zwart
blad) c.q. geheel buiten (een wit blad) de polygoon ligt of
totdat de maximale diepte van de boom (Quadtree) is
bereikt (fig. 1). Aan elk blad kan een uniek label worden
gehangen, de quadcode. Bij elke splitsing krijgen de kwa
dranten een nummer (bijvoorbeeld zuid-west 0, noord
west 1, zuid-oost 2 en noord-oost 3). Het pad van de
top naar een blad in de boom correspondeert met een
unieke string; korte strings (slechts een paar splitsingen)
komen overeen met een groot gebied, terwijl lange strings
overeenkomen met kleinere gebieden (veel splitsingen).
De ordening van punt-locaties met gehele coördinaten (of
wel de rastercellen van een tweedimensionaal grid of de Fig. 2.
tweedimensionale knopen in de Quadtree) kunnen worden De Morton-
gebruikt voor tegel-indexering (tile indexing). Hierdoor waarden (op een
wordt een tweedimensionaal probleem vertaald in een 8 bij 8grid).
ééndimensionaal probleem. In [1] [8]
[10] [12] zijn verschillende orde
ningen beschreven: row, row prime,
Morton, Hilbert, Sierpinski, Gray-
code, Cantor-diagonal en spiral. Bij
het opslaan van ruimtelijke gegevens
moet er altijd een afbeelding naar één
dimensie worden gemaakt, omdat de
tweedimensionale gegevens in het één
dimensionale geheugen van een com
puter moeten worden opgeslagen. Het
doel van de ordeningen is het cluste
ren van de ruimtelijke gegevens: objec
ten die in de werkelijkheid dicht bij
elkaar liggen, zouden ook dicht bij
elkaar in het computergeheugen (op
disk) moeten worden opgeslagen, om
dat het waarschijnlijk is dat ze ook
gezamenlijk zullen worden opgehaald.
Het bit voor bit afwisselen van de
binaire representatie van de x- en y-
coördinaat resulteert in een ééndimen
sionale sleutel: de Morton-waarde
[13]. Deze waarde is ook bekend
onder de namen Peano keyN-order of
244
1996-6
NGT GEODESIA
Region Quadtree
Morton-waarde
m
101
5
100
4
011
3
010
2
001
1
000
0
12
300
000
0
010
2
011
3
100
4
110
6
X-
111
7
(zuid-west=0, noord-west=1, zuid-oost=2, noord-oost=3)
Quadcode 0 heeft Morton interval: 0-15
Quadcode 10 heeft Morton interval: 16-19
Quadcode 12 heeft Morton interval: 24-27
Quadcode 300 heeft Morton interval: 48-48
Y 110
6
101
5
100
4
011
3
010
2
001
1
000,
0
62
0 2
b^
8
000 001 010 011 100 101 110 111
■0 1 2 3 4 5 6 7
Twee voorbeelden van Morton-waarden:
->x=001, y=010 -> xy=000110 (decimaal 6)
x=110, y=111 -> xy=111101 (decimaal 61
