NAME
Math::PlanePath::HilbertSides  sides of Hilbert curve squares
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. The square for a segment is on the left or right,
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 segments N=7to8 and N=8to9 overlap. These are consecutive segments, and nonconsecutive segments can overlap too, as for example N=27to28 and N=36to37. 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 HilbertCurve 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 returnundef
.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 straight forward 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
SEE ALSO
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoDiagonals
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
This 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/>.