Math::PlanePath::HilbertSpiral -- 2x2 self-similar spiral
use Math::PlanePath::HilbertSpiral; my $path = Math::PlanePath::HilbertSpiral->new; my ($x, $y) = $path->n_to_xy (123);
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.
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.
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.
($n_lo, $n_hi) = $path->level_to_n_range($level)
Return (0, 4**$level - 1)
.
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A059285 (etc)
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.
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::BetaOmega
http://user42.tuxfamily.org/math-planepath/index.html
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/>.