Complex Base

This pattern arises from representing a complex number in "base" i*sqrt(r). For an integer X,Y,

    base b = i*sqrt(r)
    a[j] = digit 0 to r-1
    X + Y*i*sqrt(r) = a[k]*b^k + ... + a[2]*b^2 + a[1]*b + a[0]

and N is the a[j] digits in base r

    N = a[k]*r^k + ... + a[2]*r^2 + a[1]*r + a[0]

The sum has imaginary part with a factor sqrt(r). Dividing that out gives an integer Y. For actual use as a number base, that factor can be omitted and instead fractional digits a[-1]*r^-1 etc used to reach smaller Y values, as for example in Knuth's "quater-imaginary" system of base 2*i, being i*sqrt(4), with digits 0,1,2,3. (Knuth Seminumerical Algorithms section 4.1 and CACM 1960 pp245-247.)

The powers of i in the base give the replication direction, so i^0=1 right, i^1=i up, i^2=-1 right, i^3=-i down, etc. The power of sqrt(r) then spreads the replication in the respective direction. Two steps repeat horizontally and sqrt(r)^2=r hence the doubling of 1x1 to the right, 2x2 to the left, 4x4 to the right, etc, and similarly vertically.

Negabinary

The way blocks repeat horizontally first to the right and then to the left is per the negabinary system base b=-2.

    X = x[k]*(-2)^k + ... + x[2]*(-2)^2 + x[1]*(-2) + x[0]

The effect is to represent any positive or negative X by a positive integer index NX.

    X, negabinary: ... -1 -2  0  1  2  3  4  5 ...
    index NX:           2  3  0  1  6  7  4  5

Notice how the 0 point replicates to the right as 1 and then that pair 0,1 replicates to the left as 2,3. Then the block 2,3,0,1 repeats to the right as 6,7,4,5 which the same order with 4 added to each. Then the resulting block of eight repeats to the left similarly, in the same order with 8 added to each.

"ImaginaryBase" takes the indexes NX and NY of these negabinary forms and forms N by interleaving the digits (bits) of NX and NY. That interleaving is in the style of the "ZOrderCurve".

    zX,zY = ZOrderCurve n_to_xy(N)
    X = to_negabinary(zX)
    Y = to_negabinary(zY)
    X,Y equals ImaginaryBase n_to_xy(N)

The "ZOrderCurve" replicates blocks alternately right and up, whereas for "ImaginaryBase" here it's right,up,left,down, and so on repeating.

Radix

The "radix" parameter controls the radix used to break N into X,Y. For example radix 3 replicates to make 3x1, 3x3, 9x3, 9x9, etc blocks. The replications are radix-1=2 copies of the preceding level at each stage,

    radix => 3
    +------------------------+-----------+
    | 24  25  26  15  16  17 | 6   7   8 |      2
    |                        |           |
    | 21  22  23  12  13  14 | 3   4   5 |      1
    |                        +-----------+
    | 18  19  20   9  10  11 | 0   1   2 |  <- Y=0
    +------------------------+-----------+
    | 51  52  53  42  43  44  33  34  35 |     -1
    |                                    |
    | 48  49  50  39  40  41  30  31  32 |     -2
    |                                    |
    | 45  46  47  36  37  38  27  28  29 |     -3
    |                                    |
    | 78  79  80  69  70  71  60  61  62 |     -4
    |                                    |
    | 75  76  77  66  67  68  57  58  59 |     -5
    |                                    |
    | 72  73  74  63  64  65  54  55  56 |     -6
    +------------------------------------+
                               ^
      -6  -5  -4  -3  -2  -1  X=0  1   2

X,Y are "negaternary" in this case, and similar negaradix base=-radix for higher values.

Level Methods

"($n_lo, $n_hi) = $path->level_to_n_range($level)"

Return "(0, $radix**$level - 1)".

Rectangle to N Range

The X and Y ranges can be treated separately and then interleaved,

    NXmin,NXmax = negaradix range to cover x1..x2
    NYmin,NYmax = negaradix range to cover y1..y2
    Nmin = interleave digits NXmin, NYmin
    Nmax = interleave digits NXmax, NYmax

If the NX,NY ranges are exact then the resulting Nmin,Nmax range is exact.

An exact negaradix range can be calculated by digits high to low by considering the range taken by the negaradix form. For example two negaternary digits,

    N digit              2         1         0
                   +---------+---------+---------+
    N index        | 6  7  8 | 3  4  5 | 0  1  2 |
                   +---------+---------+---------+
    X negaternary   -6 -5 -4  -3 -2 -1   0  1  2
                    ^
                   base

Taking the base=-90909...90 which is the lowest taken (where 9 is the radix digit R-1), then the next digit of N is the position from X-base, taken alternately reverse 2,1,0 as shown here or forward 0,1,2.