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. The square
47 for a segment is on the left or right,
48 -------3. .
50 v |
51 |>
52 |
53 2 .
54 |
55 |>
56 ^ |
57 0-------1 .
58 Some points are visited twice. The first is at X=2,Y=3 which is N=7
60 and N=9 where the two segments N=7to8 and N=8to9 overlap. These are
61 consecutive segments, and non-consecutive segments can overlap too, as
62 for example N=27to28 and N=36to37. Double-visited points occur also as
63 corners touching, for example at X=4,Y=3 the two N=11 N=31 touch
64 without overlapping segments.
65 The HilbertCurve squares fall within 2^k x 2^k blocks and so likewise
67 the segments here. The right side 1 to 2 and 2 to 3 don't touch the
68 2^k side. This is so of the base figure N=0 to N=4 which doesn't touch
69 X=2 and higher levels are unrotated replications so for example in the
70 N=0 to N=64 shown above X=8 is not touched. This creates rectangular
71 columns up from the X axis. Likewise rectangular rows across from the
72 Y axis, and both columns and rows inside.
73 The sides which are N=0 to N=1 and N=3 to N=4 of the base pattern
75 variously touch in higher levels giving interesting patterns of
76 squares, shapes, notches, etc.
77
79 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
80 classes.
81 "$path = Math::PlanePath::HilbertSides->new ()"
83 Create and return a new path object.
84 "($x,$y) = $path->n_to_xy ($n)"
86 Return the X,Y coordinates of point number $n on the path. Points
87 begin at 0 and if "$n < 0" then the return is an empty list.
88 "$n = $path->xy_to_n ($x,$y)"
90 Return the point number for coordinates "$x,$y". If there's
91 nothing at "$x,$y" then return "undef".
92 The curve visits an "$x,$y" twice for various points. The smaller
94 of the two N values is returned.
95 "@n_list = $path->xy_to_n_list ($x,$y)"
97 Return a list of N point numbers for coordinates "$x,$y". Points
98 may have up to two Ns for a given "$x,$y".
99
101 Coordinates
102 Difference X-Y is the same here as in the "HilbertCurve". The base
103 pattern here has N=3 at 1,2 whereas the HilbertCurve is 0,1 so X-Y is
104 the same. The two then have the same pattern of rotate 180 and/or
105 transpose in subsequent replications.
106 3
108 |
109 HilbertSides 2 3----2 HilbertCurve
110 | |
111 0----1 0----1
112 Abs dX,dY
114 abs(dY) is 1 for a vertical segment and 0 for a horizontal segment.
115 For the curve here it is
116 abs(dY) = count 1-bits of N, mod 2 = Thue-Morse binary parity
118 abs(dX) = 1 - abs(dY) = opposite
119 This is so for the base pattern N=0,1,2, and also at N=3 turning
121 towards N=4. Replication parts 1 and 2 are transposes where there is a
122 single extra 1-bit in N and dX,dY are swapped. Replication part 3 is a
123 180 degree rotation where there are two extra 1-bits in N and dX,dY are
124 negated so abs(dX),abs(dY) unchanged.
125 Turn
127 The path can turn left or right or go straight forward or 180 degree
128 reverse. Straight,reverse vs left,right is given by
129 N num trailing 0 bits turn
131 --------------------- -----------------------
132 odd straight or 180 reverse (A096268)
133 even left or right (A035263)
134 The path goes straight ahead at 2 and reverses 180 at 8 and all
136 subsequent 2*4^k.
137 Segments on Axes
139 The number of line segments on the X and Y axes 0 to 2^k, which is N=0
140 to 4^k, is
141 Xsegs[k] = 1/3*2^k + 1/2 + 1/6*(-1)^k
143 = 1, 1, 2, 3, 6, 11, 22, 43, 86 (A005578)
144 = Ysegs[k] + 1
145 Ysegs[k] = 1/3*2^k - 1/2 + 1/6*(-1)^k
147 = 0, 0, 1, 2, 5, 10, 21, 42, 85,... (A000975)
148 = binary 101010... k-1 many bits alternating
149 These counts can be calculated from the curve sub-parts
151 k odd k even
153 +---+ . . . .
155 R |>T T T
156 . . . +---+---+
157 |>T |> R<|
158 o---+ . o . +
159 The block at the origin is X and Y segments of the k-1 level. For k
161 odd, the X axis then has a transposed block which means the Y segments
162 of k-1. The Y axis has a 180 degree rotated block R. The curve is
163 symmetric in mirror image across its start to end so the count of
164 segments it puts on the Y axis is the same as Y of level k-1.
165 Xsegs[k] = Xsegs[k-1] + Ysegs[k-1] for k odd
167 Ysegs[k] = 2*Ysegs[k-1]
168 Then similarly for k even, but the other way around the 2*Y.
170 Xsegs[k] = 2*Xsegs[k-1] for k even
172 Ysegs[k] = Xsegs[k-1] + Ysegs[k-1]
173
175 Entries in Sloane's Online Encyclopedia of Integer Sequences related to
176 this path include
177 <http://oeis.org/A059285> (etc)
179 A059285 X-Y
181 A010059 abs(dX), 1 - Thue-Morse binary parity
182 A010060 abs(dY), Thue-Morse binary parity
183 A096268 turn 1=straight or reverse, 0=left or right
185 A035263 turn 0=straight or reverse, 1=left or right
186 A062880 N values on diagonal X=Y (digits 0,2 in base 4)
188 A005578 count segments on X axis, level k
190 A000975 count segments on Y axis, level k
191
193 Math::PlanePath, Math::PlanePath::HilbertCurve,
194 Math::PlanePath::PeanoDiagonals
195
197 <http://user42.tuxfamily.org/math-planepath/index.html>
198
200 Copyright 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
201 This file is part of Math-PlanePath.
203 Math-PlanePath is free software; you can redistribute it and/or modify
205 it under the terms of the GNU General Public License as published by
206 the Free Software Foundation; either version 3, or (at your option) any
207 later version.
208 Math-PlanePath is distributed in the hope that it will be useful, but
210 WITHOUT ANY WARRANTY; without even the implied warranty of
211 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
212 General Public License for more details.
213 You should have received a copy of the GNU General Public License along
215 with Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
216perl v5.36.0 2022-07-22 Math::PlanePath::HilbertSides(3)