NGT GEODESIA
1996-6
dimensie voor het betreffende niveau
in de Field-tree. Het is duidelijk dat
dit altijd minder of gelijk is dan het
beschikbare aantal gridcellen. Het to
taal aantal gridcellen per niveau in de
Field-tree is aangegeven in de kolom
#celper niveau.
Fig. 5 toont een voorbeeld waarin het
fijnste niveau „0" bestaat uit 25 m x
25 m cellen. Dit kan worden aange
past indien een groter domein nodig
is; zie ,,*25" in de kolom len cel in m.
Het grofste niveau is „7" met 3,2 km x
3,2 km cellen. Alles wat te groot is om
in het grofste niveau te passen, krijgt
een speciale SLC-waarde (bijvoor-
NRLEVELS=8 5 niveaus kan beter zijn
FINEGRID=25 II 100m kan beter zijn
THEORIGX=0
THEORIGY=0
for (i=0; kNRLEVELS; i++) do
NR[i] 2A(15-i);
SIZEji] FINEGRID 2Ai;
0R1GX[NRLEVELS-1] THEORIGX;
ORlGYjNRLEVELS-1] THEORIGY;
for (i=NRLEVELS-2; i>=0; i-) do
ORIGX[i]= ORIGXji+1] - SIZE[i+l]/4;
ORIGY[i]= ORIGY[i+l] - SIZE[i+l]/4;
II bitpatronen voor coderen niveau
BITS[MAXLEVEL]=
01000000 00000000 00000000 00000000,
00110000 00000000 00000000 00000000,
00100000 00000000 00000000 00000000,
00010000 00000000 00000000 00000000,
00001100 00000000 00000000 00000000,
00001000 00000000 00000000 00000000,
00000100 00000000 00000000 00000000,
beeld -1): de „overloopbak", welke
niet al te vol zou moeten worden. In
dien veel objecten in de overloopbak
komen, dan moet er een grover niveau
worden toegevoegd aan de Field-tree.
In het geval dat het linker-onderpunt
van het domein ligt op (0,0), dan ligt
het rechter-bovenpunt op (816,816)
in km. In de kolom oorsprong domein
(x) in m kan men zien dat fijnere
niveaus een kleine verplaatsing krijgen
in de Field-tree. Ook in fig. 3 is dit
zichtbaar.
0. SLC -1 waarde voor „niet passen"!
1get bbox max extend (in x of y dimension) -> max_ext
2. go to finest level with size>max_ext -> level [i]
3. for (j=i; j<i+3 j<NRLEVELS SLC== -1; j++) uiterlijk op niveau i+3
if (Compute_SLC_Point(j,x_min(bbox),y_min(bbox))
Compute_SLC_Pomt(j,x_max(bbox),y_max(bbox)))
SLC=Compute_SLC_Point(j,x_min(bbox),y_min(bbox))
Fig. 7.
Functie
Compute_SLC
(bbox).
Fig. 6.
Enige constanten
(algemene
oplossing).
Fig. 8.
Functie
Compute_SLC_
Point (level, x, y).
De x- en y-coördinaten van elke gridcel worden bit voor bit
afgewisseld. Dit heeft het effect van een Morton-ordening
per niveau, die weer nauw gerelateerd is aan de Quadtree
(fig. 1). De niveau-indicatie (bit-patroon, fig. 5) samen met
de Morton-waarde vormt de complete SLC-waarde van elk
mogelijk object binnen het domein.
Merk op dat deze techniek algemeen is en kan worden
aangepast met meer of minder niveaus (bijvoorbeeld 5, 8,
11 of 15) of zelfs hogere dimensies (bijvoorbeeld drie
dimensionaal). Het zou kunnen blijken dat acht niveaus
niet echt nodig zijn, gegeven een bepaalde dataset. Wan
neer slechts vijf niveaus worden gebruikt, dan moet waar
schijnlijk de afmeting van de fijnste gridcel ook groter zijn
dan 25 m om ervoor te zorgen dat er niet te veel objecten in
de overloopbak komen, bijvoorbeeld 100 m (en 1,6 km op
niveau 4).
SLC pseudo-code
De algoritmen worden in pseudo-code gegeven. De code
ringsdefinities van de Field-gridcellen zijn reeds gegeven in
fig. 5. In de pseudo-code worden de niveaus genummerd
van 0 (fijnste raster) tot 7 (grofste raster). Het grofste Field-
tree raster heeft geen (additionele) verplaatsing, de fijnere
niveaus krijgen een steeds grotere verplaatsing, zoals is te
zien in fig. 5 bij de kolom oorsprong domein (x) in m. In
fig. 6 worden enige constanten, die gebruikt worden in de
pseude-code, geïnitialiseerd. Merk op dat ORIGX[NR-
LEVELS-1] wordt geïnitialiseerd zonder additionele ver
plaatsing en dat de overige niveaus een additionele ver
plaatsing krijgen beginnend met ORIGX[NRLEVELS-2]
tot het fijnste niveau ORIGX[0].
De functie Compute_SLC (bbox) berekent de SLC van de
bboxvtm een bepaald object (fig. 7). Eerst wordt het fijnste
raster bepaald, waarin het object nog zou kunnen passen
(regels 1 en 2). Vervolgens worden het werkelijke rasterni-
veau en de SLC-waarde berekend in regel 3, door te testen
of de hoekpunten linksonder en rechtsboven van de bbox
gelijke SLC-waarden hebben. De SLC-waarde van deze
punten wordt berekend met de functie Compute_SLC_
Point (level, x, y), zoals in fig. 8 is afgebeeld.
1. x (short)trunc((x-ORIGX[level])/SIZE[level]);
y (short)trunc((y-ORIGY[leveI])/SIZE[IeveI]);
2. bitwise interleave xy -> SLC;
3. add level bitpattern (bitwise OF) -> SLC SLC BITS[level];
247
