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

In progress ...

This is a variation on the Hilbert curve which fills the plane by spiralling around X,Y negative on every second replication level.

  65--64--63--62  49--48--47  44--43--42        5
   |           |   |       |   |       |
  66--67  60--61  50--51  46--45  40--41        4
       |   |           |           |
--71  68  59  56--55  52  33--34  39--38        3
   |   |   |   |   |   |   |   |       |
  70--69  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

  -4  -3  -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 Ntopleft=4^level-1 where level is an odd number.

The parts of the curve in the X,Y negative parts are the same as the HilbertCurve, just mirrored along an anti-diagonal. For example. N=4 to N=15

HilbertSpiral                HilbertCurve
 (mirrored)                    (plain)

                            5---6   9--10
                   \        |   |   |   |
  5-- 4             \       4   7---8  11
  |                  \                  |
  6-- 7               \            13--12
      |                \            |
  9-- 8  13--14         \          14--15
  |       |   |          \
 10--11--12  15           \

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 the 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.

SEE ALSO

Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::BetaOmega