1Math::PlanePath::HilberUtsSeirdeCso(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::HilbertSides(3)
2
6 Math::PlanePath::HilbertSides -- sides of Hilbert curve squares
7
9 use Math::PlanePath::HilbertSides;
10 my $path = Math::PlanePath::HilbertSides->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This path is segments along the sides of the Hilbert curve squares as
15 per
16 F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume
18 44, 1982, pages 79-104, section 4.8 "Hilbert Curve"
19 The base pattern is N=0 to N=4. That pattern repeats transposed as
21 points N=0,4,8,12,16, etc.
22 9 | ...
24 | |
25 8 | 64----63 49----48 44----43
26 | | | | | |
27 7 | 62 50 47----46----45 42
28 | | | |
29 6 | 60----61 56 51----52 40---39,41
30 | | | | |
31 5 | 59----58---57,55--54---53,33--34----35 38
32 | | | |
33 4 | 32 36,28--37,27
34 | | | |
35 3 | 5-----6----7,9---10---11,31--30----29 26
36 | | | | |
37 2 | 4-----3 8 13----12 24---23,25
38 | | | |
39 1 | 2 14 17----18----19 22
40 | | | | | |
41 Y=0 | 0-----1 15----16 20----21
42 +-------------------------------------------------
43 X=0 1 2 3 4 5 6 7
44 If each point of the "HilbertCurve" path is taken to be a unit square
46 the effect here is to go along the sides of those squares.
47 -------3. .
49 v |
50 |>
51 |
52 2 .
53 |
54 |>
55 ^ |
56 0-------1 .
57 Some points are visited twice. The first is at X=2,Y=3 which is N=7
59 and N=9 where the two consecutive segments N=7to8 and N=8to9 overlap.
60 Non-consecutive segments can overlap too, as for example N=27to28 and
61 N=36to37 overlap. Double-visited points occur also as corners
62 touching, for example at X=4,Y=3 the two N=11 N=31 touch without
63 overlapping segments.
64 The Hilbert curve squares fall within 2^k x 2^k blocks and so likewise
66 the segments here. The right side 1 to 2 and 2 to 3 don't touch the
67 2^k side. This is so of the base figure N=0 to N=4 which doesn't touch
68 X=2 and higher levels are unrotated replications so for example in the
69 N=0 to N=64 shown above X=8 is not touched. This creates rectangular
70 columns up from the X axis. Likewise rectangular rows across from the
71 Y axis, and both columns and rows inside.
72 The sides which are N=0 to N=1 and N=3 to N=4 of the base pattern
74 variously touch in higher levels giving interesting patterns of
75 squares, shapes, notches, etc.
76
78 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
79 classes.
80 "$path = Math::PlanePath::HilbertSides->new ()"
82 Create and return a new path object.
83 "($x,$y) = $path->n_to_xy ($n)"
85 Return the X,Y coordinates of point number $n on the path. Points
86 begin at 0 and if "$n < 0" then the return is an empty list.
87 "$n = $path->xy_to_n ($x,$y)"
89 Return the point number for coordinates "$x,$y". If there's
90 nothing at "$x,$y" then return "undef".
91 The curve visits an "$x,$y" twice for various points. The smaller
93 of the two N values is returned.
94 "@n_list = $path->xy_to_n_list ($x,$y)"
96 Return a list of N point numbers for coordinates "$x,$y". Points
97 may have up to two Ns for a given "$x,$y".
98
100 Coordinates
101 Difference X-Y is the same here as in the "HilbertCurve". The base
102 pattern here has N=3 at 1,2 whereas the HilbertCurve is 0,1 so X-Y is
103 the same. The two then have the same pattern of rotate 180 and/or
104 transpose in subsequent replications.
105 3
107 |
108 HilbertSides 2 3----2 HilbertCurve
109 | |
110 0----1 0----1
111 Abs dX,dY
113 abs(dY) is 1 for a vertical segment and 0 for a horizontal segment.
114 For the curve here it is
115 abs(dY) = count 1-bits of N, mod 2 = Thue-Morse binary parity
117 abs(dX) = 1 - abs(dY) = opposite
118 This is so for the base pattern N=0,1,2, and also at N=3 turning
120 towards N=4. Replication parts 1 and 2 are transposes where there is a
121 single extra 1-bit in N and dX,dY are swapped. Replication part 3 is a
122 180 degree rotation where there are two extra 1-bits in N and dX,dY are
123 negated so abs(dX),abs(dY) unchanged.
124 Turn
126 The path can turn left or right or go forward straight or 180 degree
127 reverse. Straight,reverse vs left,right is given by
128 N num trailing 0 bits turn
130 --------------------- -----------------------
131 odd straight or 180 reverse (A096268)
132 even left or right (A035263)
133 The path goes straight ahead at 2 and reverses 180 at 8 and all
135 subsequent 2*4^k.
136 Segments on Axes
138 The number of line segments on the X and Y axes 0 to 2^k, which is N=0
139 to 4^k, is
140 Xsegs[k] = 1/3*2^k + 1/2 + 1/6*(-1)^k
142 = 1, 1, 2, 3, 6, 11, 22, 43, 86 (A005578)
143 = Ysegs[k] + 1
144 Ysegs[k] = 1/3*2^k - 1/2 + 1/6*(-1)^k
146 = 0, 0, 1, 2, 5, 10, 21, 42, 85,... (A000975)
147 = binary 101010... k-1 many bits alternating
148 These counts can be calculated from the curve sub-parts
150 k odd k even
152 +---+ . . . .
154 R |>T T T
155 . . . +---+---+
156 |>T |> R<|
157 o---+ . o . +
158 The block at the origin is X and Y segments of the k-1 level. For k
160 odd the X axis then has a transposed block which means the Y segments
161 of k-1. The Y axis has a 180 degree rotated block R. The curve is
162 symmetric in mirror image across its start to end so the count of
163 segments it puts on the Y axis is the same as Y of level k-1.
164 Xsegs[k] = Xsegs[k-1] + Ysegs[k-1] for k odd
166 Ysegs[k] = 2*Ysegs[k-1]
167 Then similarly for k even, but the other way around the 2*Y.
169 Xsegs[k] = 2*Xsegs[k-1] for k even
171 Ysegs[k] = Xsegs[k-1] + Ysegs[k-1]
172
174 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
175 this path include
176 <http://oeis.org/A059285> (etc)
178 A059285 X-Y
180 A010059 abs(dX), 1 - Thue-Morse binary parity
181 A010060 abs(dY), Thue-Morse binary parity
182 A096268 turn 1=straight or reverse, 0=left or right
184 A035263 turn 0=straight or reverse, 1=left or right
185 A062880 N values on diagonal X=Y (digits 0,2 in base 4)
187 A005578 count segments on X axis, level k
189 A000975 count segments on Y axis, level k
190
192 Math::PlanePath, Math::PlanePath::HilbertCurve
193
195 <http://user42.tuxfamily.org/math-planepath/index.html>
196
198 Copyright 2015, 2016, 2017, 2018, 2019 Kevin Ryde
199 This file is part of Math-PlanePath.
201 Math-PlanePath is free software; you can redistribute it and/or modify
203 it under the terms of the GNU General Public License as published by
204 the Free Software Foundation; either version 3, or (at your option) any
205 later version.
206 Math-PlanePath is distributed in the hope that it will be useful, but
208 WITHOUT ANY WARRANTY; without even the implied warranty of
209 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
210 General Public License for more details.
211 You should have received a copy of the GNU General Public License along
213 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
214perl v5.30.0 2019-08-17 Math::PlanePath::HilbertSides(3)