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.
47
48            -------3.       .
49               v   |
50                   |>
51                   |
52                   2        .
53                   |
54                   |>
55               ^   |
56           0-------1        .
57
58       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
65       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
73       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

FUNCTIONS

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

FORMULAS

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

OEIS

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

SEE ALSO

192       Math::PlanePath, Math::PlanePath::HilbertCurve
193

HOME PAGE

195       <http://user42.tuxfamily.org/math-planepath/index.html>
196

LICENSE

198       Copyright 2015, 2016, 2017, 2018, 2019 Kevin Ryde
199
200       This file is part of Math-PlanePath.
201
202       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
207       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
212       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/>.
214
215
216
217perl v5.32.0                      2020-07-28  Math::PlanePath::HilbertSides(3)
Impressum