Math::PlanePath::ZOrderCurve -- 2x2 self-similar Z shape digits
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);
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.
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.
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
$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).
radix
($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.
$n
$n < 0
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.
$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.
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).
Math::PlanePath, Math::PlanePath::PeanoCurve, Math::PlanePath::HilbertCurve
http://www.jjj.de/fxt/#fxtbook (section 1.31.2)
http://www.jjj.de/fxt/#fxtbook
Algorithm::QuadTree
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.