1Math::PlanePath::HilberUtsSeirdeCso(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::HilbertSides(3)
2
3
4

NAME

6       Math::PlanePath::HilbertSides -- sides of Hilbert curve squares
7

SYNOPSIS

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

DESCRIPTION

14       This path is segments along the sides of the Hilbert curve squares as
15       per
16
17           F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume
18           44, 1982, pages 79-104, section 4.8 "Hilbert Curve"
19
20       The base pattern is N=0 to N=4.  That pattern repeats transposed as
21       points N=0,4,8,12,16, etc.
22
23             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
45       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
49            -------3.       .
50               v   |
51                   |>
52                   |
53                   2        .
54                   |
55                   |>
56               ^   |
57           0-------1        .
58
59       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
66       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
74       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

FUNCTIONS

79       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
80       classes.
81
82       "$path = Math::PlanePath::HilbertSides->new ()"
83           Create and return a new path object.
84
85       "($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
89       "$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
93           The curve visits an "$x,$y" twice for various points.  The smaller
94           of the two N values is returned.
95
96       "@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

FORMULAS

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
107                             3
108                             |
109           HilbertSides      2         3----2    HilbertCurve
110                             |              |
111                        0----1         0----1
112
113   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
117           abs(dY) = count 1-bits of N, mod 2 = Thue-Morse binary parity
118           abs(dX) = 1 - abs(dY)              = opposite
119
120       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
126   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
130           N num trailing 0 bits               turn
131           ---------------------      -----------------------
132                 odd                  straight or 180 reverse     (A096268)
133                 even                 left or right               (A035263)
134
135       The path goes straight ahead at 2 and reverses 180 at 8 and all
136       subsequent 2*4^k.
137
138   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
142           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
146           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
150       These counts can be calculated from the curve sub-parts
151
152             k odd              k even
153
154           +---+   .          .   .   .
155             R |>T              T   T
156           .   .   .          +---+---+
157               |>T            |>    R<|
158           o---+   .          o   .   +
159
160       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
166           Xsegs[k] = Xsegs[k-1] +   Ysegs[k-1]       for k odd
167           Ysegs[k] =              2*Ysegs[k-1]
168
169       Then similarly for k even, but the other way around the 2*Y.
170
171           Xsegs[k] = 2*Xsegs[k-1]                    for k even
172           Ysegs[k] =   Xsegs[k-1] + Ysegs[k-1]
173

OEIS

175       Entries in Sloane's Online Encyclopedia of Integer Sequences related to
176       this path include
177
178           <http://oeis.org/A059285> (etc)
179
180           A059285    X-Y
181           A010059    abs(dX), 1 - Thue-Morse binary parity
182           A010060    abs(dY), Thue-Morse binary parity
183
184           A096268    turn 1=straight or reverse, 0=left or right
185           A035263    turn 0=straight or reverse, 1=left or right
186
187           A062880    N values on diagonal X=Y (digits 0,2 in base 4)
188
189           A005578    count segments on X axis, level k
190           A000975    count segments on Y axis, level k
191

SEE ALSO

193       Math::PlanePath, Math::PlanePath::HilbertCurve,
194       Math::PlanePath::PeanoDiagonals
195

HOME PAGE

197       <http://user42.tuxfamily.org/math-planepath/index.html>
198

LICENSE

200       Copyright 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
201
202       This file is part of Math-PlanePath.
203
204       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
209       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
214       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/>.
216
217
218
219perl v5.36.0                      2022-07-22  Math::PlanePath::HilbertSides(3)
Impressum