/ 
Math-PlanePath-25
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::ZOrderCurve

NAME

Math::PlanePath::ZOrderCurve -- 2x2 self-similar Z shape quadrant traversal

SYNOPSIS

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

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.

FUNCTIONS

$path = Math::PlanePath::ZOrderCurve->new ()

Create and return a new path object.

($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 simply 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.

N Range

Within each row the N values increase as X increases, and conversely within each column N increases with increasing Y. 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::HilbertCurve, Math::PlanePath::PeanoCurve

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

Algorithm::QuadTree

HOME PAGE

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

LICENSE

Math-PlanePath is Copyright 2010, 2011 Kevin Ryde

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/>.