A
Z-order. Een voorbeeld: kolom 1
001 bin» regel 2 01 O^in heeft Morton-
waarde 6 000110i,;n (fig. 2). De
Morton-waarde heeft verschillende
relaties met de Quadtree. Zoals in
fig. 1 duidelijk is te zien, heeft iedere
quadcode een directe vertaling naar
een interval van Morton-waarden.
Een korte quadcode-string is gerela
teerd aan een lang interval van Mor
ton-waarden en een lange quadcode-
string is gerelateerd aan een kort inter
val van Morton-waarden.
In [1] zijn drie wenselijke eigenschap
pen van ruimtelijke ordeningen gede
finieerd:
Fig. 3.
De Field-tree
(getoond met drie
niveaus).
continu indien de cellen behorende
bij elk paar opeenvolgende waarden
echte 4-buren zijn (d.w.z. direct
boven, onder, links of rechts van
elkaar liggen);
kivadrant-recursief indien de cellen
binnen ieder geldig (sub)kwadrant
van de Quadtree corresponderen
met een reeks opeenvolgende gehele
getallen als waarden;
monotoon indien voor iedere gege
ven x de waarden monotoon varië
ren in de y-richting en omgekeerd.
Abel en Mark [1] concluderen uit hun
praktische vergelijkingen van vijf ver
schillende ordeningen (zij nemen
Cantor-diagonal, Spiral- en Sierpins-
ki-ordeningen niet mee) dat over het
algemeen de Morton-ordening en de
Hilbert-ordening de beste alternatie
ven zijn. In [9] wordt bewezen dat de
verwachte afstand tussen de waarden
die horen bij twee (4-)buren op een
grid van n bij n cellen (n+l)/2 is voor zowel Morton- als
Hilbert- (en ook voor row en row-prime) ordeningen.
Echter de gemiddelde verste afstand van twee buren in de
Morton-ordening is hoger dan die binnen de Hilbert-
ordening [5].
De Field-tree kan polygonen en polylijnen opslaan op een
niet-gefragmenteerde manier. De Field-tree is één van de
weinige structuren waarbij er rekening mee wordt gehou
den dat geometrische objecten een verschillende belang
rijkheid kunnen hebben. Gedurende het laatste decennium
is een aantal varianten van de Field-tree gepubliceerd in [6]
[7]. Hier zal de aandacht worden gericht op de Partition
Field-tree. Conceptueel gezien bestaat de Field-tree uit ver
schillende lagen van grids, elk met een eigen resolutie en
een eigen verplaatsing van de oorsprong (fig. 3). Een grid-
cel wordt een field genoemd. Eigenlijk is de Field-tree geen
hiërarchische zoekboom, maar een gerichte acyclische
graaf. Elke field (knoop) kan één, twee of vier voorgangers
hebben. Binnen een laag vormen de fields tezamen een
partitie en overlappen dus niet.
Een nieuw object wordt opgeslagen binnen het kleinste
field waarin het geheel past. Als gevolg van de verschillende
oorsprong-verplaatsingen wordt een object nooit meer dan
drie niveaus boven het kleinste field waarin het object wat
betreft grootte zou kunnen passen, opgeslagen. Merk op
dat dit niet het geval is bij Quadtree-achtige structuren,
omdat de grenzen op de verschillende niveaus colineair
zijn. Een nadeel van de Field-tree is dat een overlooppagina
soms nodig is, bijvoorbeeld omdat het niet mogelijk is een
relatief groot of belangrijk object binnen een overvol field
in een lager niveau te plaatsen.
SLC
Waarom kan een SLC-waarde niet direct worden gebaseerd
op een quadcode (of interval van Morton-waarden)? Er zijn
twee mogelijke opties, maar beide hebben een nadeel:
elk object krijgt één quadcode. Echter een klein object
dat één van de hoofdsplitsingsranden doorsnijdt, krijgt
een korte quadcode string. Het is duidelijk dat zo'n groot
gebied geen goede benadering is voor het betreffende
object;
elk object zou meerdere quadcodes kunnen krijgen. De
bijbehorende gebieden benaderen tezamen het object
beter, maar het geheel is te complex om efficiënt binnen
een DBMS te kunnen worden gebruikt (bij elk object
behoort een verzameling quadcodes).
De Field-tree is gebruikt voor een betere benadering van
een object door één enkele waarde: het betreffende field
waarin het object wordt opgeslagen. Dankzij de verschoven
grids van de Field-tree krijgen kleine objecten nooit een
waarde die overeenkomt met een groot gebied. De SLC
codeert zowel de gridcel (bijvoorbeeld een Morton-waarde)
als het gridniveau in één enkele waarde. De SLC-methode,
zoals al kort is beschreven in de introductie, kan worden
gebruikt in SQL (Structured Query Language) (zoek)op-
-
-
245
NGT GEODESIA
1996-6
Field-tree
max domein
1
I
I
1
1
r
1
1
I
1
1
1
1
1
1
r
1
i
i
1
i
1
r
1
i
1
1
1
1
1
1
t-
1
1
1
1
l
l
V-
1
1
i
l
I
l
u
1
1
l
1
1
1
U
H -
L
1
1
J
J
J
_l
Oorsnronn niveau 13x31
Oorsprong niveau 1(7x7)
Oorsprong niveau n (15x15)
