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

FUNCTIONS

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

FORMULAS

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

SEE ALSO

315       Math::PlanePath, Math::PlanePath::DekkingCentres,
316       Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
317

HOME PAGE

319       <http://user42.tuxfamily.org/math-planepath/index.html>
320

LICENSE

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