1Math::PlanePath::DekkinUgsCeurrvCeo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::DekkingCurve(3)
2
3
4

NAME

6       Math::PlanePath::DekkingCurve -- 5x5 self-similar edge curve
7

SYNOPSIS

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

DESCRIPTION

14       This is an integer version of a 5x5 self-similar curve from
15
16           F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume
17           44, 1982, pages 79-104, section 4.9 "Gosper-Type Curves"
18
19       This is also a horizontal mirror image of the E-curve from
20
21           Douglas M. McKenna, "SquaRecurves, E-Tours, Eddies, and Frenzies:
22           Basic Families of Peano Curves on the Square Grid", in "The Lighter
23           Side of Mathematics: Proceedings of the Eugene Strens Memorial
24           Conference on Recreational Mathematics and its History",
25           Mathematical Association of America, 1994, pages 49-73, ISBN
26           0-88385-516-X
27
28       The base pattern is N=0 to N=25.  It repeats with rotations or
29       reversals which make the ends join.  For example N=75 to N=100 is the
30       base pattern in reverse, ie. from N=25 down to N=0.  Or N=50 to N=75 is
31       reverse and also rotate by -90.
32
33           10 |             123-124-125-...      86--85
34              |               |                   |   |
35            9 | 115-116-117 122-121  90--89--88--87  84
36              |   |       |       |   |               |
37            8 | 114-113 118-119-120  91--92--93  82--83
38              |       |                       |   |
39            7 |     112 107-106 103-102  95--94  81  78--77
40              |       |   |   |   |   |   |       |   |   |
41            6 |     111 108 105-104 101  96--97  80--79  76
42              |       |   |           |       |           |
43            5 |     110-109  14--15 100--99--98  39--40  75          66--65
44              |               |   |               |   |   |           |   |
45            4 |  10--11--12--13  16  35--36--37--38  41  74  71--70  67  64
46              |   |               |   |               |   |   |   |   |   |
47            3 |   9---8---7  18--17  34--33--32  43--42  73--72  69--68  63
48              |           |   |               |   |                       |
49            2 |       5---6  19  22--23  30--31  44  47--48  55--56--57  62--61
50              |       |       |   |   |   |       |   |   |   |       |       |
51            1 |       4---3  20--21  24  29--28  45--46  49  54--53  58--59--60
52              |           |           |       |           |       |
53           Y=0|   0---1---2          25--26--27          50--51--52
54              +----------------------------------------------------------------
55                X=0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
56
57       The curve segments correspond to edges of squares in a 5x5 arrangement.
58
59            +     +     +    14----15     +
60                              |  v  |>
61               ^     ^       <|     |
62           10----11----12----13    16     +
63            |              v        |>
64            |>       ^           ^  |
65            9-----8-----7    18----17     +
66               v  |     |     |>
67                     ^  |>    |        ^
68            +     5-----6    19    22----23
69                  |          <|     |    <|
70                 <|  ^        |    <|     |
71            +     4-----3    20----21 -- 24
72                        |       v        <|
73               ^     ^  |>                |
74            0-----1-----2     +     +    25
75
76       The little notch marks show which square each edge represents and which
77       it expands into at the next level.  For example N=1 to N=2 has its
78       notch on the left so the next level N=25 to N=50 expands on the left.
79
80       All the directions are made by rotating the base pattern.  When the
81       expansion is on the right the segments go in reverse.  For example N=2
82       to N=3 expands on the right and is made by rotating the base pattern
83       clockwise 90 degrees.  This means that N=2 becomes the 25 end, and
84       following the curve to the 0 start at N=3.
85
86       Dekking writes these directions as a sequence of 25 symbols s(i,j)
87       where i=0 for left plain or i=1 for right reversal and j=0,1,2,3
88       direction j*90 degrees anti-clockwise so E,N,W,S.
89
90   Arms
91       The optional "arms" parameter can give up to four copies of the curve,
92       each advancing successively.  Each copy is in a successive quadrant.
93
94           arms => 3                |
95                             67-70-73       42-45                  5
96                              |              |  |
97                    43-46-49 64-61 30-33-36-39 48                  4
98                     |     |     |  |           |
99                    40-37 52-55-58 27-24-21 54-51                  3
100                        |                 |  |
101                       34 19-16  7--4 15-18 57 66-69               2
102                        |  |  |  |  |  |     |  |  |
103                       31 22 13-10  1 12--9 60-63 72               1
104                        |  |              |        |
105               ...--74 28-25  5--2  0--3--6       75-...     <-- Y=0
106                     |        |
107                    71 62-59  8-11                                -1
108                     |  |  |     |
109                    68-65 56 17-14                                -2
110                           |  |
111                       50-53 20-23-26                             -3
112                        |           |
113                       47 38-35-32-29                             -4
114                        |  |
115                       44-41                                      -5
116                                    ^
117                ... -5 -4 -3 -2 -1 X=0 1  2  3  4  5 ...
118
119       The origin is N=0 and is on the first arm only.  The second and
120       subsequent arms begin 1,2,etc.  The curves interleave perfectly on the
121       axes where the arms meet.  The result is that arms=4 fills the plane
122       visiting each integer X,Y exactly once and not touching or crossing.
123

FUNCTIONS

125       See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
126       classes.
127
128       "$path = Math::PlanePath::DekkingCurve->new ()"
129       "$path = Math::PlanePath::DekkingCurve->new (arms => $a)"
130           Create and return a new path object.
131
132           The optional "arms" parameter gives between 1 and 4 copies of the
133           curve successively advancing.
134
135       "($x,$y) = $path->n_to_xy ($n)"
136           Return the X,Y coordinates of point number $n on the path.  Points
137           begin at 0 and if "$n < 0" then the return is an empty list.
138
139   Level Methods
140       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
141           Return "(0, 25**$level)", or for multiple arms return "(0, $arms *
142           25**$level)".
143
144           There are 25^level + 1 points in a level, numbered starting from 0.
145           On the second and third arms the origin is omitted (so as not to
146           repeat that point) and so just 25^level for them, giving 25^level+1
147           + (arms-1)*25^level = arms*25^level + 1 many points starting from
148           0.
149

FORMULAS

151   X Axis Segments
152       In the sample points above there are some line segments on the X axis.
153       A segment X to X+1 is traversed or not according to
154
155           X digits in base 5
156
157           traversed        if X==0
158           traversed        if low digit 1
159           not-traversed    if low digit 2 or 3 or 4
160           when low digit == 0
161             traversed      if lowest non-zero 1 or 2
162             not-traversed  if lowest non-zero 3 or 4
163
164           XsegPred(X) = 1,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,...
165            =1 at 0,1,5,6,10,11,16,21,25,26,30,31,35,36,41,...
166
167       In the samples the segments at X=1, X=6 and X=11 segments traversed are
168       low digit 1.  Their preceding X=5 and X=10 segments are low digit==0
169       and the lowest non-zero 1 or 2 (respectively).  At X=15 however the
170       lowest non-zero is 3 and so not-traversed there.
171
172       In general in groups of 5 there is always X==1 mod 5 traversed but its
173       preceding X==0 mod 5 is traversed or not according to lowest non-zero
174       1,2 or 3,4.
175
176       This pattern is found by considering how the base pattern expands.  The
177       plain base pattern has its south edge on the X axis.  The first two
178       sub-parts of that south edge are the base pattern unrotated, so the
179       south edge again, but the other parts rotated.  In general the sides
180       are
181
182                  0 1 2 3 4
183           S  ->  S,S,E,N,W
184           E  ->  S,S,E,N,N
185           N  ->  W,S,E,N,N
186           W  ->  W,S,E,N,W
187
188       Starting in S and taking digits high to low a segment is traversed when
189       the final state is S again.
190
191       Any digit 1,2,3 goes to S,E,N respectively.  If no 1,2,3 at all then S
192       start.  At the lowest 1,2,3 there are only digits 0,4 below.  If no
193       such digits then only digit 1 which is S, or no digits at all for N=0,
194       is traversed.  If one or more 0s below then E goes to S so a lowest
195       non-zero 2 means traversed too.  If there is any 4 then it goes to N or
196       W and in those states both 0,4 stay in N or W so not-traversed.
197
198       The transitions from the lowest 1,2,3 can be drawn in a state diagram,
199
200                      +--+
201                      v  |4                           base 5 digits of X
202                      North  <---+    <-------+       high to low
203                    /            |            |
204                   /0            |4           |
205                  /              |            |3
206           +->   v               |       2    |
207           |   West             East  <--- start lowest 1,2,3
208           +--   ^               |            |
209           0,4    \              |            |1
210                   \4            |0           |or no 1,2,3 at all
211                    \            |            |
212                      South  <---+    <-------+
213                      ^  |0
214                      +--+
215
216       The full diagram, starting from the top digit, is less clear
217
218                      +--+
219                      v  |3,4
220               +--->  North  <---+
221              3|    /  | ^  \    |3,4
222               |   /0  1 |  2\   |              base 5 digits of X
223               |  /    | |    \  |              high to low
224           +-> | v     | |     v |   <-+
225           |   West 2---------> East   |        start in South,
226           +-- | ^     | |     ^ |   --+        segment traversed
227           0,4 |  \    | |    /  |    2         if end in South
228               |   \4  | 3  2/   |
229              1|    \  v |  /    |0,1
230               +--->  South  <---+
231                      ^  |0,1
232                      +--+
233
234       but allows usual DFA state machine manipulations to reverse to go low
235       to high.
236
237                 +---------- start ----------+
238                 |       1    0|   2,3,4     |         base 5 digits of X
239                 |             |             |         low to high
240                 v       1,2   v   3,4       v
241           traversed <------- m1 -------> not-traversed
242                             0| ^
243                              +-+
244
245       In state m1 a 0 digit loops back to m1 so finds the lowest non-zero.
246       States start and m1 are the same except for the behaviour of digit 2
247       and so in the rules above the result for digit 2 differs according to
248       whether there are any low 0s.
249
250   Y Axis Segments
251       The Y axis can be treated similarly
252
253           Y digits in base 5  (with a single 0 digit if Y==0)
254
255           traversed        if lowest digit 3
256           not-traversed    if lowest digit 0 or 1 or 2
257           when lowest digit == 4
258             traversed      if lowest non-4 is 2 or 3
259             not-traversed  if lowest non-4 is 0 or 1
260
261           YsegPred(X) = 0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,...
262            =1 at 3,8,13,14,18,19,23,28,33,38,39,43,44,48,...
263
264       The Y axis goes around the base square clockwise, so the digits are
265       reversed 0<->4 from the X axis for the state transitions.  The initial
266       state is W.
267
268                  0 1 2 3 4
269           S  ->  W,N,E,S,S
270           E  ->  N,N,E,S,S
271           N  ->  N,N,E,S,W
272           W  ->  W,N,E,S,W
273
274       N and W can be merged as equivalent.  Their only difference is digit 0
275       going to N or W and both of those are final result not-traversed.
276
277       Final state S is reached if the lowest digit is 3, or if state S or E
278       are reached by digit 2 or 3 and then only 4s below.
279
280   X,Y Axis Interleaving
281       For arms=2 the second copy of the curve is rotated +90 degrees, and
282       similarly a third or fourth copy in arms=3 or 4.  This means each axis
283       is a Y axis of the quadrant before and an X axis of the quadrant after.
284       When this happens the segments do not overlap nor does the curve touch.
285
286       This is seen from the digit rules above.  The 1 mod 5 segment is always
287       traversed by X and never by Y.  The 2 mod 5 segment is never traversed
288       by either.  The 3 mod 5 segment is always traversed by Y and never by
289       X.
290
291       The 0 mod 5 segment is sometimes traversed by X, and never by Y.  The 4
292       mod 5 segment is sometimes traversed by Y, and never by Y.
293
294               0       1       2       3       4
295           *-------*-------*-------*-------*-------*
296               X       X    neither    Y       Y
297             maybe                            maybe
298
299       A 4 mod 5 segment has one or more trailing 4s and at +1 for the next
300       segment they become 0s and increment the lowest non-4.
301
302           +--------+-----+-------+
303           |  ...   |  d  | 4...4 |   N   == 4 mod 5    X never
304           +--------+-----+-------+                     Y maybe
305
306           +--------+-----+-------+
307           |  ...   | d+1 | 0...0 |   N+1 == 0 mod 5    X maybe
308           +--------+-----+-------+                     Y never
309
310       Per the Y rule, a 4 mod 5 segment is traversed when d=2,3.  The
311       following segment is then d+1=3,4 as lowest non-zero which in the X
312       rule is not-traversed.  Conversely in the Y rule not-traversed when
313       d=0,1 which becomes d+1=1,2 which in the X rule is traversed.
314
315       So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are
316       traversed.
317
318           XsegPred(X) or YsegPred = 1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,...
319            =1 at 0,1,3,5,6,8,10,11,13,14,16,18,19,21,23,25,...
320

SEE ALSO

322       Math::PlanePath, Math::PlanePath::DekkingCentres,
323       Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
324

HOME PAGE

326       <http://user42.tuxfamily.org/math-planepath/index.html>
327

LICENSE

329       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
330       Kevin Ryde
331
332       This file is part of Math-PlanePath.
333
334       Math-PlanePath is free software; you can redistribute it and/or modify
335       it under the terms of the GNU General Public License as published by
336       the Free Software Foundation; either version 3, or (at your option) any
337       later version.
338
339       Math-PlanePath is distributed in the hope that it will be useful, but
340       WITHOUT ANY WARRANTY; without even the implied warranty of
341       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
342       General Public License for more details.
343
344       You should have received a copy of the GNU General Public License along
345       with Math-PlanePath.  If not, see <http://www.gnu.org/licenses/>.
346
347
348
349perl v5.34.0                      2021-07-22  Math::PlanePath::DekkingCurve(3)
Impressum