1Math::PlanePath::DekkinUgsCeurrvCeo(n3t)ributed Perl DocMuamtehn:t:aPtliaonnePath::DekkingCurve(3)
2
6 Math::PlanePath::DekkingCurve -- 5x5 self-similar edge curve
7
9 use Math::PlanePath::DekkingCurve;
10 my $path = Math::PlanePath::DekkingCurve->new;
11 my ($x, $y) = $path->n_to_xy (123);
12
14 This is an integer version of a 5x5 self-similar curve from
15 F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume
17 44, 1982, pages 79-104, section 4.9 "Gosper-Type Curves"
18 This is a horizontal mirror image of the E-curve of McKenna (1978).
20 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 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 The curve segments correspond to edges of squares in a 5x5 arrangement.
51 + + + 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 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 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 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 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 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 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
118 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
119 classes.
120 "$path = Math::PlanePath::DekkingCurve->new ()"
122 "$path = Math::PlanePath::DekkingCurve->new (arms => $a)"
123 Create and return a new path object.
124 The optional "arms" parameter gives between 1 and 4 copies of the
126 curve successively advancing.
127 "($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 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 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
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 X digits in base 5
149 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 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 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 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 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 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 Starting in S and taking digits high to low a segment is traversed when
182 the final state is S again.
183 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 The transitions from the lowest 1,2,3 can be drawn in a state diagram,
192 +--+
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 The full diagram, starting from the top digit, is less clear
210 +--+
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 but allows usual DFA state machine manipulations to reverse to go low
228 to high.
229 +---------- 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 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 Y Axis Segments
244 The Y axis can be treated similarly
245 Y digits in base 5 (with a single 0 digit if Y==0)
247 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 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 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 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 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 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 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 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 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 0 1 2 3 4
288 *-------*-------*-------*-------*-------*
289 X X neither Y Y
290 maybe maybe
291 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 +--------+-----+-------+
296 | ... | d | 4...4 | N == 4 mod 5 X never
297 +--------+-----+-------+ Y maybe
298 +--------+-----+-------+
300 | ... | d+1 | 0...0 | N+1 == 0 mod 5 X maybe
301 +--------+-----+-------+ Y never
302 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 So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are
309 traversed.
310 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
315 Math::PlanePath, Math::PlanePath::DekkingCentres,
316 Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
317
319 <http://user42.tuxfamily.org/math-planepath/index.html>
320
322 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018 Kevin Ryde
323 This file is part of Math-PlanePath.
325 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 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 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/>.
338perl v5.30.0 2019-08-17 Math::PlanePath::DekkingCurve(3)