1Math::PlanePath::HilberUtsSeprirCaoln(t3r)ibuted Perl DoMcautmhe:n:tPaltainoenPath::HilbertSpiral(3)
2
6 Math::PlanePath::HilbertSpiral -- 2x2 self-similar spiral
7
9 use Math::PlanePath::HilbertSpiral;
10 my $path = Math::PlanePath::HilbertSpiral->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
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 ..--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 -2 -1 X=0 1 2 3 4 5
34 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 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 HilbertSpiral HilbertCurve
45 \ 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 This mirroring has the effect of mapping
59 HilbertCurve X,Y -> -Y,-X for HilbertSpiral
61 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 Level Ranges
67 Reckoning the initial N=0 to N=3 as level 1, a replication level
68 extends to
69 Nstart = 0
71 Nlevel = 4^level - 1 (inclusive)
72 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 width = height = Xmax - Xmin
79 = Ymax - Ymin
80 = 2^level - 1
81 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 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 The power-of-4 formulas above for Ymin/Ymax have the effect of
98 producing alternating bit patterns like this.
99 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
104 See "FUNCTIONS" in Math::PlanePath for behaviour common to all path
105 classes.
106 "$path = Math::PlanePath::HilbertSpiral->new ()"
108 Create and return a new path object.
109 "($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 "($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 Level Methods
119 "($n_lo, $n_hi) = $path->level_to_n_range($level)"
120 Return "(0, 4**$level - 1)".
121
123 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
124 this path include
125 <http://oeis.org/A059285> (etc)
127 A059285 X-Y coordinate diff
129 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
135 Math::PlanePath, Math::PlanePath::HilbertCurve,
136 Math::PlanePath::BetaOmega
137
139 <http://user42.tuxfamily.org/math-planepath/index.html>
140
142 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
143 Kevin Ryde
144 This file is part of Math-PlanePath.
146 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 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 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/>.
159perl v5.34.0 2021-07-22 Math::PlanePath::HilbertSpiral(3)