++ed by:
Kevin Ryde
and 1 contributors

# NAME

Math::PlanePath::ZOrderCurve -- 2x2 self-similar Z shape digits

# SYNOPSIS

`````` use Math::PlanePath::ZOrderCurve;

my \$path = Math::PlanePath::ZOrderCurve->new;
my (\$x, \$y) = \$path->n_to_xy (123);

# or another radix digits ...
my \$path3 = Math::PlanePath::ZOrderCurve->new (radix => 3);``````

# DESCRIPTION

This path puts points in a self-similar Z pattern described by G.M. Morton,

``````      7  |   42  43  46  47  58  59  62  63
6  |   40  41  44  45  56  57  60  61
5  |   34  35  38  39  50  51  54  55
4  |   32  33  36  37  48  49  52  53
3  |   10  11  14  15  26  27  30  31
2  |    8   9  12  13  24  25  28  29
1  |    2   3   6   7  18  19  22  23
Y=0 |    0   1   4   5  16  17  20  21  64  ...
+--------------------------------
X=0   1   2   3   4   5   6   7``````

The first four points make a "Z" shape if written with Y going downwards (inverted if drawn upwards as above),

``````     0---1       Y=0
/
/
2---3       Y=1``````

Then groups of those are arranged as a further Z, etc, doubling in size each time.

``````     0   1      4   5       Y=0
2   3 ---  6   7       Y=1
/
/
/
8   9 --- 12  13       Y=2
10  11     14  15       Y=3``````

Within an power of 2 square 2x2, 4x4, 8x8, 16x16 etc (2^k)x(2^k), all the N values 0 to 2^(2*k)-1 are within the square. The top right corner 3, 15, 63, 255 etc of each is the 2^(2*k)-1 maximum.

## Power of 2 Values

Plotting N values related to powers of 2 can come out as interesting patterns. For example displaying the N's which have no digit 3 in their base 4 representation gives

``````    *
* *
*   *
* * * *
*       *
* *     * *
*   *   *   *
* * * * * * * *
*               *
* *             * *
*   *           *   *
* * * *         * * * *
*       *       *       *
* *     * *     * *     * *
*   *   *   *   *   *   *   *
* * * * * * * * * * * * * * * * ``````

The 0,1,2 and not 3 makes a little 2x2 "L" at the bottom left, then repeating at 4x4 with again the whole "3" position undrawn, and so on. This is the Sierpinski triangle (a rotated version of Math::PlanePath::SierpinskiTriangle). The blanks are also a visual representation of 1-in-4 cross-products saved by recursive use of the Karatsuba multiplication algorithm.

Plotting the fibbinary numbers (eg. Math::NumSeq::Fibbinary) which are N values with no adjacent 1 bits in binary makes an attractive tree-like pattern,

``````    *
**
*
****
*
**
*   *
********
*
**
*
****
*       *
**      **
*   *   *   *
****************
*                               *
**                              **
*                               *
****                            ****
*                               *
**                              **
*   *                           *   *
********                        ********
*               *               *               *
**              **              **              **
*               *               *               *
****            ****            ****            ****
*       *       *       *       *       *       *       *
**      **      **      **      **      **      **      **
*   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *
****************************************************************``````

The horizontals arise from N=...0a0b0c for bits a,b,c so Y=...000 and X=...abc, making those N values adjacent. Similarly N=...a0b0c0 for a vertical.

The radix parameter can do the same sort of N -> X/Y digit splitting in a higher base. For example radix 3 makes 3x3 groupings,

``````      5  |  33  34  35  42  43  44
4  |  30  31  32  39  40  41
3  |  27  28  29  36  37  38  45  ...
2  |   6   7   8  15  16  17  24  25  26
1  |   3   4   5  12  13  14  21  22  23
Y=0 |   0   1   2   9  10  11  18  19  20
+--------------------------------------
X=0   1   2   3   4   5   6   7   8``````

# FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

`\$path = Math::PlanePath::ZOrderCurve->new ()`
`\$path = Math::PlanePath::ZOrderCurve->new (radix => \$r)`

Create and return a new path object. The optional `radix` parameter gives the base for digit splitting (the default is binary, radix 2).

`(\$x,\$y) = \$path->n_to_xy (\$n)`

Return the X,Y coordinates of point number `\$n` on the path. Points begin at 0 and if `\$n < 0` then the return is an empty list.

Fractional positions give an X,Y position along a straight line between the integer positions. The lines don't overlap, but the lines between bit squares soon become rather long and probably of very limited use.

`\$n = \$path->xy_to_n (\$x,\$y)`

Return an integer point number for coordinates `\$x,\$y`. Each integer N is considered the centre of a unit square and an `\$x,\$y` within that square returns N.

# FORMULAS

## N to X,Y

The coordinate calculation is simple. The bits of X and Y are every second bit of N. So if N = binary 101010 then X=000 and Y=111 in binary, which is the N=42 shown above at X=0,Y=7.

With the `radix` parameter the digits are treated likewise, in the given radix rather than binary.

## Rectangle to N Range

Within each row the N values increase as X increases, and within each column N increases with increasing Y (for all `radix` parameters).

So for a given rectangle the smallest N is at the lower left corner (smallest X and smallest Y), and the biggest N is at the upper right (biggest X and biggest Y).

`http://www.jjj.de/fxt/#fxtbook` (section 1.31.2)

http://user42.tuxfamily.org/math-planepath/index.html