Figure 1 shows a quadtree representation with three levels.
Each smallest quadrant is labeled with its corresponding Peano
code. A cutting line is defined as Ax + By + C = 0. For each
cutting line, we get the slope K from the equation as K = -A/B.
We further decompose K to the x-component Kx = 1 (or -B/A)
and y-component Ky = -A/B (or 1).
<
211 23] 29] 311.53] 551.61] 63
20) 22] 28] 30| 52| 54] 60} 62
A N %
17] 19] 25] 27] 49] 51] 57] 59
16] 18] 24 | 26| 48] 50] 56] 58
13 15| 37 | 39-75) 47
N &%ü +
9 | 11| 33] 35] 411 43
7
L-—'
4 | 6-17] 14| 36| 38| 44| 46
3
2
8 | 10] 32]| 34| 40] 42
© 1 2 3 4 5 6G. .a X
Figure 1 Line Cutting on a Quadtree Representation
For each cutting line, the intersecting points with the boundary
of the quadtree representation are determined. The Peano
codes of those intersecting points can then be calculated simply
by interleaving the x and y coordinates. Once we get the two
intersecting points, the next step is to search for those
quadrants along the cutting line. The final step is to remove the
front quadrants.
1) Determine the intersecting points
In Figure 1, the cutting lines l; is defined as:
li: x -4y* 8 7 0, K=-AB=1/,
Kx, K,=-A/B= 1/4.
The binary expressions of K, and K, are K, = 01 @, Ky = 2” (10)
= 0.01 o Ko, is then the interleaving of Kx and Ky, Kp) =
10.0001 o.
Note the calculation of Ky is different because decimal digits
are involved. We use the 2" components to express the decimal
part. If n = -1, we set a 1 at the first digit after the decimal
point of binary number. If n = -2, we set a | at the second digit
after the decimal point. This is similar for the subsequent
digits. The order of interleaving for the decimal part is the
same as for the integer part.
The starting intersecting point of the line with the boundary x
= 0 is Pi (0, 2).
2) Determine the Peano code for the starting quadrant
Once we have the starting intersecting point, the next step is to
calculate the Peano code for the starting quadrant.
Let PC[0] denote the Peano code for the staring quadrant of the
line. We could then calculate PC[0] by interleaving the x- and
y-coordinate. For example, for point P; (0, 2)
x70 97000
y72097100
PC[0] 20100 $7 4 (10)
3) Search for the quadrants along the cutting line
To search for the remaining quadrants along the cutting line,
we have to use the information about x- and y-components of
the slope. To propogate from one point to its next point along
the cutting line, the following equation is used:
PC[i] * PC[i-1] o + K o.
To demonstrate the usage of the above equation, the searching
procedure along 1; is shown as follows:
PC[0] =4 (10) = 0100 Q)
PC[1]=PC[0]+K@=0100@+10.0001n
=01l 10.0001 @ = 6.06 qo
In the above binary addition, if an increment occurs at a digit
of x-component, then it will pass the increment to the higher
digit of x-component, instead of the next direct digit. The same
holds for y-components.
If the resulted Peano code is not an integer, the integer part is
used as the code of the linear quadtree. The decimal part is
kept for searching further quadrants along the cutting line.
PC[2]=PC[1]0110.0001g+10.00010
=11 00.01 002 = 12.2509
PC[3] 2 PC[2]1100.010059 * 10.000 1o
=1110.0101w= 143100
PC[4]2 PC[3]1 110.0101909*10.000 1o
-100101.000090 7 3700
PC[5] - PC[4] 320010 1.000 055 10.000 1o)
=100111.000 17 = 39.06 (10)
PC[6] -PC[5] 1000111.000 159 * 10.000 1o)
2101101.01009 245.5 qo
PC[7] 2PC[6]1 01101.01005 10.000109
=101111.0101@ =4731 ao
Consequently, the Peano codes in the list are 4, 6, 12, 14, 37,
39, 45 and 47.
Once all the Peano codes along the cutting line are detected,
the front quadrants can be removed.
3.2 Datum adjustment algorithm based on Peano codes
Datum adjustment is an operation in subsurface modeling to
stretch the bottom surface of a layer So to a plane. The top
510
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B4. Vienna 1996
2)4
Cast
Cast
3) C
1) /
bou
have
2.1)
Sinc
coor
Sim
3
10—
54—
2.2)
thei
COOI
part
