Math::PlanePath::HilbertSides -- sides of hilbert curve squares
use Math::PlanePath::HilbertSides; my $path = Math::PlanePath::HilbertSides->new; my ($x, $y) = $path->n_to_xy (123);
This path is segments along the sides of the Hilbert curve squares in the manner of
F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages 79-104, section 4.8 "Hilbert Curve"
The base pattern is N=0 to N=4. That pattern repeats transposed as points N=0,4,8,12,16, etc.
9 | ... | | 8 | 64----63 49----48 44----43 | | | | | | 7 | 62 50 47----46----45 42 | | | | 6 | 60----61 56 51----52 40---39,41 | | | | | 5 | 59----58---57,55--54---53,33--34----35 38 | | | | 4 | 32 36,28--37,27 | | | | 3 | 5-----6----7,9---10---11,31--30----29 26 | | | | | 2 | 4-----3 8 13----12 24---23,25 | | | | 1 | 2 14 17----18----19 22 | | | | | | Y=0 | 0-----1 15----16 20----21 +------------------------------------------------- X=0 1 2 3 4 5 6 7
If each point of the HilbertCurve path is taken to be a unit square the effect here is to go along the sides of those squares.
HilbertCurve
-------3. . v | |> | 2 . | |> ^ | 0-------1 .
Some points are visited twice. The first is N=7,9 at X=2,Y=3 where consecutive segments overlapping. Later at N=11,31 corners touch. The segments N=27,28 and N=36,37 are a non-consecutive segment overlap.
The Hilbert curve squares fall within 2^k x 2^k blocks and so likewise the segments here. The right side 1 to 2 and 2 to 3 don't touch the 2^k side. This is so of the base figure N=0 to N=4 which doesn't touch X=2 and higher levels are unrotated replications so for example in the N=0 to N=64 shown above X=8 is not touched. This creates rectangular columns up from the X axis, and likewise rows from the Y axis, and both columns and rows within that pattern.
The sides which are N=0 to N=1 and N=3 to N=4 of the base pattern variously touch in higher levels giving interesting patterns of squares, shapes, notches, etc.
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::HilbertSides->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.
$n
$n < 0
$n = $path->xy_to_n ($x,$y)
Return the point number for coordinates $x,$y. If there's nothing at $x,$y then return undef.
$x,$y
undef
The curve visits an $x,$y twice for various points. The smaller of the two N values is returned.
@n_list = $path->xy_to_n_list ($x,$y)
Return a list of N point numbers for coordinates $x,$y. Points may have up to two Ns for a given $x,$y.
Difference X-Y is the same here as in the HilbertCurve. The base pattern here has 3 at 1,2 where the HilbertCurve is 0,1 so X-Y is the same. The two then have the same pattern of rotate 180 and/or transpose in subsequent replications.
3 | HilbertSides 2 3----2 HilbertCurve | | 0----1 0----1
abs(dY) is given by the Thue-Morse binary parity (count 1-bits, mod 2) of N, and abs(dX) its opposite. This is so for the base pattern N=0,1,2, and also at N=3 turning towards N=4. Replication parts 1 and 2 are transposes where a single extra 1-bit in N swaps dX,dY. Replication part 3 is a 180 degree rotation where 2 extra 1-bits in N is abs(dX),abs(dY) unchanged.
The path goes straight ahead at 2 and reverses 180 at 8 and subsequent 2*4^k. The replications then mean that in general if there are n trailing 0-bits on N then n odd is straight or reverse, and n even is turn left or right.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A059285 (etc)
A059285 X-Y A010059 abs(dX), 1 - Thue-Morse binary parity A010060 abs(dY), Thue-Morse binary parity A096268 turn 1=straight or reverse, 0=left or right A035263 turn 0=straight or reverse, 1=left or right A062880 N values on diagonal X=Y (digits 0,2 in base 4)
Math::PlanePath, Math::PlanePath::HilbertCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2015 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.