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 also a horizontal mirror image of the E-curve from
20 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 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 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 The curve segments correspond to edges of squares in a 5x5 arrangement.
58 + + + 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 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 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 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 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 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 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
125 See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path
126 classes.
127 "$path = Math::PlanePath::DekkingCurve->new ()"
129 "$path = Math::PlanePath::DekkingCurve->new (arms => $a)"
130 Create and return a new path object.
131 The optional "arms" parameter gives between 1 and 4 copies of the
133 curve successively advancing.
134 "($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 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 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
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 X digits in base 5
156 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 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 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 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 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 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 Starting in S and taking digits high to low a segment is traversed when
189 the final state is S again.
190 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 The transitions from the lowest 1,2,3 can be drawn in a state diagram,
199 +--+
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 The full diagram, starting from the top digit, is less clear
217 +--+
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 but allows usual DFA state machine manipulations to reverse to go low
235 to high.
236 +---------- 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 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 Y Axis Segments
251 The Y axis can be treated similarly
252 Y digits in base 5 (with a single 0 digit if Y==0)
254 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 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 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 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 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 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 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 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 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 0 1 2 3 4
295 *-------*-------*-------*-------*-------*
296 X X neither Y Y
297 maybe maybe
298 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 +--------+-----+-------+
303 | ... | d | 4...4 | N == 4 mod 5 X never
304 +--------+-----+-------+ Y maybe
305 +--------+-----+-------+
307 | ... | d+1 | 0...0 | N+1 == 0 mod 5 X maybe
308 +--------+-----+-------+ Y never
309 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 So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are
316 traversed.
317 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
322 Math::PlanePath, Math::PlanePath::DekkingCentres,
323 Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
324
326 <http://user42.tuxfamily.org/math-planepath/index.html>
327
329 Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020
330 Kevin Ryde
331 This file is part of Math-PlanePath.
333 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 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 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/>.
346perl v5.34.0 2021-07-22 Math::PlanePath::DekkingCurve(3)