and 1 contributors

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

http://user42.tuxfamily.org/math-planepath/index.html