Install Now
Math::PlanePath::HilbertSides -- sides of Hilbert curve squares
Contents
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 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. The square for a segment is on the left or right,
-------3. .
v |
|>
|
2 .
|
|>
^ |
0-------1 .
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 non-consecutive segments can overlap too,
as for example N=27to28 and N=36to37. Double-visited 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.
Formulas
Coordinates
Difference X-Y 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 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
AbsdX,dY
abs(dY) is 1 for a vertical segment and 0 for a horizontal segment. For the curve here it is
abs(dY) = count 1-bits of N, mod 2 = Thue-Morse 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 1-bit in N and dX,dY are swapped. Replication part 3 is a
180 degree rotation where there are two extra 1-bits 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.
SegmentsonAxes
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... k-1 many bits alternating
These counts can be calculated from the curve sub-parts
k odd k even
+---+ . . . .
R |>T T T
. . . +---+---+
|>T |> R<|
o---+ . o . +
The block at the origin is X and Y segments of the k-1 level. For k odd, the X axis then has a
transposed block which means the Y segments of k-1. 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 k-1.
Xsegs[k] = Xsegs[k-1] + Ysegs[k-1] for k odd
Ysegs[k] = 2*Ysegs[k-1]
Then similarly for k even, but the other way around the 2*Y.
Xsegs[k] = 2*Xsegs[k-1] for k even
Ysegs[k] = Xsegs[k-1] + Ysegs[k-1]
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".
Home Page
License
Copyright 2015, 2016, 2017, 2018, 2019, 2020 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/>.
perl v5.32.0 2021-01-23 Math::PlanePath::HilbertSides(3pm)
Name
Math::PlanePath::HilbertSides -- sides of Hilbert curve squares
Oeis
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)
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
Synopsis
use Math::PlanePath::HilbertSides;
my $path = Math::PlanePath::HilbertSides->new;
my ($x, $y) = $path->n_to_xy (123);
PNG Icons
