NAME¶
Math::PlanePath::HilbertSpiral -- 2x2 self-similar spiral
SYNOPSIS¶
use Math::PlanePath::HilbertSpiral;
my $path = Math::PlanePath::HilbertSpiral->new;
my ($x, $y) = $path->n_to_xy (123);
DESCRIPTION¶
This is a Hilbert curve variation which fills the plane by spiralling around
into negative X,Y on every second replication level.
..--63--62 49--48--47 44--43--42 5
| | | | |
60--61 50--51 46--45 40--41 4
| | |
59 56--55 52 33--34 39--38 3
| | | | | | |
58--57 54--53 32 35--36--37 2
|
5-- 4-- 3-- 2 31 28--27--26 1
| | | | |
6-- 7 0-- 1 30--29 24--25 <- Y=0
| |
9-- 8 13--14 17--18 23--22 -1
| | | | | |
10--11--12 15--16 19--20--21 -2
-2 -1 X=0 1 2 3 4 5
The curve starts with the same N=0 to N=3 as the "HilbertCurve", then
the following 2x2 blocks N=4 to N=15 go around in negative X,Y. The top-left
corner for this negative direction is at Ntopleft=4^level-1 for an odd
numbered level.
The parts of the curve in the X,Y negative parts are the same as the plain
"HilbertCurve", just mirrored along the anti-diagonal. For example.
N=4 to N=15
HilbertSpiral HilbertCurve
\ 5---6 9--10
\ | | | |
\ 4 7---8 11
\ |
5-- 4 \ 13--12
| \ |
6-- 7 \ 14--15
| \
9-- 8 13--14 \
| | | \
10--11--12 15
This mirroring has the effect of mapping
HilbertCurve X,Y -> -Y,-X for HilbertSpiral
Notice the coordinate difference (-Y)-(-X) = X-Y so that difference,
representing a projection onto the X=-Y opposite diagonal, is the same in both
paths.
Level Ranges¶
Reckoning the initial N=0 to N=3 as level 1, a replication level extends to
Nstart = 0
Nlevel = 4^level - 1 (inclusive)
Xmin = Ymin = - (4^floor(level/2) - 1) * 2 / 3
= binary 1010...10
Xmax = Ymax = (4^ceil(level/2) - 1) / 3
= binary 10101...01
width = height = Xmax - Xmin
= Ymax - Ymin
= 2^level - 1
The X,Y range doubles alternately above and below, so the result is a 1 bit
going alternately to the max or min, starting with the max for level 1.
level X,Ymin binary X,Ymax binary
----- --------------- --------------
0 0 0
1 0 0 1 = 1
2 -2 = -10 1 = 01
3 -2 = -010 5 = 101
4 -10 = -1010 5 = 0101
5 -10 = -01010 21 = 10101
6 -42 = -101010 21 = 010101
7 -42 = -0101010 85 = 1010101
The power-of-4 formulas above for Ymin/Ymax have the effect of producing
alternating bit patterns like this.
This is the same sort of level range as "BetaOmega" has on its Y
coordinate, but on this "HilbertSpiral" it applies to both X and Y.
FUNCTIONS¶
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
classes.
- "$path = Math::PlanePath::HilbertSpiral->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_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1,
$x2,$y2)"
- The returned range is exact, meaning $n_lo and $n_hi are the smallest and
biggest in the rectangle.
Level Methods¶
- "($n_lo, $n_hi) = $path->level_to_n_range($level)"
- Return "(0, 4**$level - 1)".
OEIS¶
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this
path include
A059285 X-Y coordinate diff
The difference X-Y is the same as the "HilbertCurve", since the
"negative" spiral parts are mirrored across the X=-Y anti-diagonal,
which means coordinates (-Y,-X) and -Y-(-X) = X-Y.
SEE ALSO¶
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::BetaOmega
HOME PAGE¶
<
http://user42.tuxfamily.org/math-planepath/index.html>
LICENSE¶
Copyright 2011, 2012, 2013, 2014 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/>.