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. The blanks are a visual representation of the multiplications saved by recursive use of the Karatsuba multiplication algorithm.

Radix

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

$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 and 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).

SEE ALSO

Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve, Math::PlanePath::ImaginaryBase

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

Algorithm::QuadTree

HOME PAGE

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

LICENSE

Copyright 2010, 2011 Kevin Ryde

This file is part of Math-PlanePath.

Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-PlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.

cpanm Math::PlanePath

perl -MCPAN -e shell
install Math::PlanePath