NAME
Math::PlanePath::HilbertSpiral  2x2 selfsimilar 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.
..6362 494847 444342 5
    
6061 5051 4645 4041 4
  
59 5655 52 3334 3938 3
      
5857 5453 32 353637 2

5 4 3 2 31 282726 1
    
6 7 0 1 3029 2425 < Y=0
 
9 8 1314 1718 2322 1
     
101112 1516 192021 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 topleft corner for this negative direction is at Ntopleft=4^level1 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 antidiagonal. For example. N=4 to N=15
HilbertSpiral HilbertCurve
\ 56 910
\    
\ 4 78 11
\ 
5 4 \ 1312
 \ 
6 7 \ 1415
 \
9 8 1314 \
   \
101112 15
This mirroring has the effect of mapping
HilbertCurve X,Y > Y,X for HilbertSpiral
Notice the coordinate difference (Y)(X) = XY 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 powerof4 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.
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A059285 (etc)
A059285 XY coordinate diff
The difference XY is the same as the HilbertCurve
, since the "negative" spiral parts are mirrored across the X=Y antidiagonal, which means coordinates (Y,X) and Y(X) = XY.
SEE ALSO
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::BetaOmega
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014 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/>.