SYNOPSIS
use Math::PlanePath::HilbertSides;
my $path = Math::PlanePath::HilbertSides>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This path is segments along the sides of the Hilbert curve squares as per
 F. M. Dekking, ``Recurrent Sets'', Advances in Mathematics, volume 44, 1982, pages 79104, 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  6463 4948 4443       7  62 50 474645 42     6  6061 56 5152 4039,41      5  595857,555453,333435 38     4  32 36,2837,27     3  567,91011,313029 26      2  43 8 1312 2423,25     1  2 14 171819 22       Y=0  01 1516 2021 + 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.
3. . v  >  2 .  > ^  01 .
Some points are visited twice. The first is at X=2,Y=3 which is N=7 and N=9 where the two consecutive segments N=7to8 and N=8to9 overlap. Nonconsecutive segments can overlap too, as for example N=27to28 and N=36to37 overlap. Doublevisited points occur also as corners touching, for example at X=4,Y=3 the two N=11 N=31 touch without overlapping segments.
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. Likewise rectangular rows across from the Y axis, and both columns and rows inside.
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.
FUNCTIONS
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 = $path>xy_to_n ($x,$y)"

Return the point number for coordinates "$x,$y". If there's nothing at
"$x,$y" then return "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".
FORMULAS
Coordinates
Difference XY is the same here as in the "HilbertCurve". The base pattern here has N=3 at 1,2 whereas the HilbertCurve is 0,1 so XY is the same. The two then have the same pattern of rotate 180 and/or transpose in subsequent replications.
3  HilbertSides 2 32 HilbertCurve   01 01
Abs dX,dY
abs(dY) is 1 for a vertical segment and 0 for a horizontal segment. For the curve here it is
abs(dY) = count 1bits of N, mod 2 = ThueMorse binary parity abs(dX) = 1  abs(dY) = 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 there is a single extra 1bit in N and dX,dY are swapped. Replication part 3 is a 180 degree rotation where there are two extra 1bits in N and dX,dY are negated so abs(dX),abs(dY) unchanged.
Turn
The path can turn left or right or go forward straight or 180 degree reverse. Straight,reverse vs left,right is given by
N num trailing 0 bits turn   odd straight or 180 reverse (A096268) even left or right (A035263)
The path goes straight ahead at 2 and reverses 180 at 8 and all subsequent 2*4^k.
Segments on Axes
The number of line segments on the X and Y axes 0 to 2^k, which is N=0 to 4^k, is
Xsegs[k] = 1/3*2^k + 1/2 + 1/6*(1)^k = 1, 1, 2, 3, 6, 11, 22, 43, 86 (A005578) = Ysegs[k] + 1 Ysegs[k] = 1/3*2^k  1/2 + 1/6*(1)^k = 0, 0, 1, 2, 5, 10, 21, 42, 85,... (A000975) = binary 101010... k1 many bits alternating
These counts can be calculated from the curve subparts
k odd k even ++ . . . . R >T T T . . . +++ >T > R< o+ . o . +
The block at the origin is X and Y segments of the k1 level. For k odd the X axis then has a transposed block which means the Y segments of k1. The Y axis has a 180 degree rotated block R. The curve is symmetric in mirror image across its start to end so the count of segments it puts on the Y axis is the same as Y of level k1.
Xsegs[k] = Xsegs[k1] + Ysegs[k1] for k odd Ysegs[k] = 2*Ysegs[k1]
Then similarly for k even, but the other way around the 2*Y.
Xsegs[k] = 2*Xsegs[k1] for k even Ysegs[k] = Xsegs[k1] + Ysegs[k1]
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
 <http://oeis.org/A059285> (etc)
A059285 XY A010059 abs(dX), 1  ThueMorse binary parity A010060 abs(dY), ThueMorse 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) A005578 count segments on X axis, level k A000975 count segments on Y axis, level k
LICENSE
Copyright 2015, 2016 Kevin RydeThis file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.