1Math::PlanePath::HilberUtsSeprirCaoln(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::HilbertSpiral(3)
2
3
4

NAME

6       Math::PlanePath::HilbertSpiral -- 2x2 self-similar spiral
7

SYNOPSIS

9        use Math::PlanePath::HilbertSpiral;
10        my $path = Math::PlanePath::HilbertSpiral->new;
11        my ($x, $y) = $path->n_to_xy (123);
12

DESCRIPTION

14       This is a Hilbert curve variation which fills the plane by spiralling
15       around into negative X,Y on every second replication level.
16
17           ..--63--62  49--48--47  44--43--42        5
18                    |   |       |   |       |
19               60--61  50--51  46--45  40--41        4
20                |           |           |
21               59  56--55  52  33--34  39--38        3
22                |   |   |   |   |   |       |
23               58--57  54--53  32  35--36--37        2
24                                |
25                5-- 4-- 3-- 2  31  28--27--26        1
26                |           |   |   |       |
27                6-- 7   0-- 1  30--29  24--25    <- Y=0
28                    |                   |
29                9-- 8  13--14  17--18  23--22       -1
30                |       |   |   |   |       |
31               10--11--12  15--16  19--20--21       -2
32
33               -2  -1  X=0  1   2   3   4   5
34
35       The curve starts with the same N=0 to N=3 as the "HilbertCurve", then
36       the following 2x2 blocks N=4 to N=15 go around in negative X,Y.  The
37       top-left corner for this negative direction is at Ntopleft=4^level-1
38       for an odd numbered level.
39
40       The parts of the curve in the X,Y negative parts are the same as the
41       plain "HilbertCurve", just mirrored along the anti-diagonal.  For
42       example. N=4 to N=15
43
44           HilbertSpiral             HilbertCurve
45
46                         \        5---6   9--10
47                          \       |   |   |   |
48                           \      4   7---8  11
49                            \                 |
50             5-- 4           \           13--12
51             |                \           |
52             6-- 7             \         14--15
53                 |              \
54             9-- 8  13--14       \
55             |       |   |        \
56            10--11--12  15
57
58       This mirroring has the effect of mapping
59
60           HilbertCurve X,Y  ->  -Y,-X for HilbertSpiral
61
62       Notice the coordinate difference (-Y)-(-X) = X-Y so that difference,
63       representing a projection onto the X=-Y opposite diagonal, is the same
64       in both paths.
65
66   Level Ranges
67       Reckoning the initial N=0 to N=3 as level 1, a replication level
68       extends to
69
70           Nstart = 0
71           Nlevel = 4^level - 1    (inclusive)
72
73           Xmin = Ymin = - (4^floor(level/2) - 1) * 2 / 3
74                       = binary 1010...10
75           Xmax = Ymax = (4^ceil(level/2) - 1) / 3
76                       = binary 10101...01
77
78           width = height = Xmax - Xmin
79                          = Ymax - Ymin
80                          = 2^level - 1
81
82       The X,Y range doubles alternately above and below, so the result is a 1
83       bit going alternately to the max or min, starting with the max for
84       level 1.
85
86           level     X,Ymin   binary      X,Ymax  binary
87           -----     ---------------      --------------
88             0         0                    0
89             1         0          0         1 =       1
90             2        -2 =      -10         1 =      01
91             3        -2 =     -010         5 =     101
92             4       -10 =    -1010         5 =    0101
93             5       -10 =   -01010        21 =   10101
94             6       -42 =  -101010        21 =  010101
95             7       -42 = -0101010        85 = 1010101
96
97       The power-of-4 formulas above for Ymin/Ymax have the effect of
98       producing alternating bit patterns like this.
99
100       This is the same sort of level range as "BetaOmega" has on its Y
101       coordinate, but on this "HilbertSpiral" it applies to both X and Y.
102

FUNCTIONS

104       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
105       classes.
106
107       "$path = Math::PlanePath::HilbertSpiral->new ()"
108           Create and return a new path object.
109
110       "($x,$y) = $path->n_to_xy ($n)"
111           Return the X,Y coordinates of point number $n on the path.  Points
112           begin at 0 and if "$n < 0" then the return is an empty list.
113
114       "($n_lo, $n_hi) = $path->rect_to_n_range ($x1,$y1, $x2,$y2)"
115           The returned range is exact, meaning $n_lo and $n_hi are the
116           smallest and biggest in the rectangle.
117
118   Level Methods
119       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
120           Return "(0, 4**$level - 1)".
121

OEIS

123       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
124       this path include
125
126           <http://oeis.org/A059285> (etc)
127
128           A059285    X-Y coordinate diff
129
130       The difference X-Y is the same as the "HilbertCurve", since the
131       "negative" spiral parts are mirrored across the X=-Y anti-diagonal,
132       which means coordinates (-Y,-X) and -Y-(-X) = X-Y.
133

SEE ALSO

135       Math::PlanePath, Math::PlanePath::HilbertCurve,
136       Math::PlanePath::BetaOmega
137

HOME PAGE

139       <http://user42.tuxfamily.org/math-planepath/index.html>
140

LICENSE

142       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
143       Kevin Ryde
144
145       This file is part of Math-PlanePath.
146
147       Math-PlanePath is free software; you can redistribute it and/or modify
148       it under the terms of the GNU General Public License as published by
149       the Free Software Foundation; either version 3, or (at your option) any
150       later version.
151
152       Math-PlanePath is distributed in the hope that it will be useful, but
153       WITHOUT ANY WARRANTY; without even the implied warranty of
154       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
155       General Public License for more details.
156
157       You should have received a copy of the GNU General Public License along
158       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
159
160
161
162perl v5.34.0                      2021-07-22 Math::PlanePath::HilbertSpiral(3)
Impressum