NAME
Math::PlanePath::DekkingCurve  5x5 selfsimilar edge curve
SYNOPSIS
use Math::PlanePath::DekkingCurve;
my $path = Math::PlanePath::DekkingCurve>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an integer version of a 5x5 selfsimilar curve from
F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages 79104, section 4.9 "GosperType Curves"
This is also a horizontal mirror image of the Ecurve from
Douglas M. McKenna, "SquaRecurves, ETours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid", in "The Lighter Side of Mathematics: Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History", Mathematical Association of America, 1994, pages 4973, ISBN 088385516X
The base pattern is N=0 to N=25. It repeats with rotations or reversals which make the ends join. For example N=75 to N=100 is the base pattern in reverse, ie. from N=25 down to N=0. Or N=50 to N=75 is reverse and also rotate by 90.
10  123124125... 8685
   
9  115116117 122121 90898887 84
     
8  114113 118119120 919293 8283
   
7  112 107106 103102 9594 81 7877
         
6  111 108 105104 101 9697 8079 76
     
5  110109 1415 1009998 3940 75 6665
       
4  10111213 16 35363738 41 74 7170 67 64
         
3  987 1817 343332 4342 7372 6968 63
     
2  56 19 2223 3031 44 4748 555657 6261
           
1  43 2021 24 2928 4546 49 5453 585960
     
Y=0 012 252627 505152
+
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The curve segments correspond to edges of squares in a 5x5 arrangement.
+ + + 1415 +
 v >
^ ^ < 
10111213 16 +
 v >
> ^ ^ 
987 1817 +
v   >
^ >  ^
+ 56 19 2223
 <  <
< ^  < 
+ 43 2021  24
 v <
^ ^ > 
012 + + 25
The little notch marks show which square each edge represents and which it expands into at the next level. For example N=1 to N=2 has its notch on the left so the next level N=25 to N=50 expands on the left.
All the directions are made by rotating the base pattern. When the expansion is on the right the segments go in reverse. For example N=2 to N=3 expands on the right and is made by rotating the base pattern clockwise 90 degrees. This means that N=2 becomes the 25 end, and following the curve to the 0 start at N=3.
Dekking writes these directions as a sequence of 25 symbols s(i,j) where i=0 for left plain or i=1 for right reversal and j=0,1,2,3 direction j*90 degrees anticlockwise so E,N,W,S.
Arms
The optional arms
parameter can give up to four copies of the curve, each advancing successively. Each copy is in a successive quadrant.
arms => 3 
677073 4245 5
  
434649 6461 30333639 48 4
    
4037 525558 272421 5451 3
  
34 1916 74 1518 57 6669 2
        
31 22 1310 1 129 6063 72 1
   
...74 2825 52 036 75... < Y=0
 
71 6259 811 1
   
6865 56 1714 2
 
5053 202326 3
 
47 38353229 4
 
4441 5
^
... 5 4 3 2 1 X=0 1 2 3 4 5 ...
The origin is N=0 and is on the first arm only. The second and subsequent arms begin 1,2,etc. The curves interleave perfectly on the axes where the arms meet. The result is that arms=4 fills the plane visiting each integer X,Y exactly once and not touching or crossing.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::DekkingCurve>new ()
$path = Math::PlanePath::DekkingCurve>new (arms => $a)

Create and return a new path object.
The optional
arms
parameter gives between 1 and 4 copies of the curve successively advancing. ($x,$y) = $path>n_to_xy ($n)

Return the X,Y coordinates of point number
$n
on the path. Points begin at 0 and if$n < 0
then the return is an empty list.
Level Methods
($n_lo, $n_hi) = $path>level_to_n_range($level)

Return
(0, 25**$level)
, or for multiple arms return(0, $arms * 25**$level)
.There are 25^level + 1 points in a level, numbered starting from 0. On the second and third arms the origin is omitted (so as not to repeat that point) and so just 25^level for them, giving 25^level+1 + (arms1)*25^level = arms*25^level + 1 many points starting from 0.
FORMULAS
X Axis Segments
In the sample points above there are some line segments on the X axis. A segment X to X+1 is traversed or not according to
X digits in base 5
traversed if X==0
traversed if low digit 1
nottraversed if low digit 2 or 3 or 4
when low digit == 0
traversed if lowest nonzero 1 or 2
nottraversed if lowest nonzero 3 or 4
XsegPred(X) = 1,1,0,0,0,1,1,0,0,0,1,1,0,0,0,0,1,0,...
=1 at 0,1,5,6,10,11,16,21,25,26,30,31,35,36,41,...
In the samples the segments at X=1, X=6 and X=11 segments traversed are low digit 1. Their preceding X=5 and X=10 segments are low digit==0 and the lowest nonzero 1 or 2 (respectively). At X=15 however the lowest nonzero is 3 and so nottraversed there.
In general in groups of 5 there is always X==1 mod 5 traversed but its preceding X==0 mod 5 is traversed or not according to lowest nonzero 1,2 or 3,4.
This pattern is found by considering how the base pattern expands. The plain base pattern has its south edge on the X axis. The first two subparts of that south edge are the base pattern unrotated, so the south edge again, but the other parts rotated. In general the sides are
0 1 2 3 4
S > S,S,E,N,W
E > S,S,E,N,N
N > W,S,E,N,N
W > W,S,E,N,W
Starting in S and taking digits high to low a segment is traversed when the final state is S again.
Any digit 1,2,3 goes to S,E,N respectively. If no 1,2,3 at all then S start. At the lowest 1,2,3 there are only digits 0,4 below. If no such digits then only digit 1 which is S, or no digits at all for N=0, is traversed. If one or more 0s below then E goes to S so a lowest nonzero 2 means traversed too. If there is any 4 then it goes to N or W and in those states both 0,4 stay in N or W so nottraversed.
The transitions from the lowest 1,2,3 can be drawn in a state diagram,
++
v 4 base 5 digits of X
North <+ <+ high to low
/  
/0 4 
/  3
+> v  2 
 West East < start lowest 1,2,3
+ ^  
0,4 \  1
\4 0 or no 1,2,3 at all
\  
South <+ <+
^ 0
++
The full diagram, starting from the top digit, is less clear
++
v 3,4
+> North <+
3 /  ^ \ 3,4
 /0 1  2\  base 5 digits of X
 /   \  high to low
+>  v   v  <+
 West 2> East  start in South,
+  ^   ^  + segment traversed
0,4  \   /  2 if end in South
 \4  3 2/ 
1 \ v  / 0,1
+> South <+
^ 0,1
++
but allows usual DFA state machine manipulations to reverse to go low to high.
+ start +
 1 0 2,3,4  base 5 digits of X
   low to high
v 1,2 v 3,4 v
traversed < m1 > nottraversed
0 ^
++
In state m1 a 0 digit loops back to m1 so finds the lowest nonzero. States start and m1 are the same except for the behaviour of digit 2 and so in the rules above the result for digit 2 differs according to whether there are any low 0s.
Y Axis Segments
The Y axis can be treated similarly
Y digits in base 5 (with a single 0 digit if Y==0)
traversed if lowest digit 3
nottraversed if lowest digit 0 or 1 or 2
when lowest digit == 4
traversed if lowest non4 is 2 or 3
nottraversed if lowest non4 is 0 or 1
YsegPred(X) = 0,0,0,1,0,0,0,0,1,0,0,0,0,1,1,0,0,...
=1 at 3,8,13,14,18,19,23,28,33,38,39,43,44,48,...
The Y axis goes around the base square clockwise, so the digits are reversed 0<>4 from the X axis for the state transitions. The initial state is W.
0 1 2 3 4
S > W,N,E,S,S
E > N,N,E,S,S
N > N,N,E,S,W
W > W,N,E,S,W
N and W can be merged as equivalent. Their only difference is digit 0 going to N or W and both of those are final result nottraversed.
Final state S is reached if the lowest digit is 3, or if state S or E are reached by digit 2 or 3 and then only 4s below.
X,Y Axis Interleaving
For arms=2 the second copy of the curve is rotated +90 degrees, and similarly a third or fourth copy in arms=3 or 4. This means each axis is a Y axis of the quadrant before and an X axis of the quadrant after. When this happens the segments do not overlap nor does the curve touch.
This is seen from the digit rules above. The 1 mod 5 segment is always traversed by X and never by Y. The 2 mod 5 segment is never traversed by either. The 3 mod 5 segment is always traversed by Y and never by X.
The 0 mod 5 segment is sometimes traversed by X, and never by Y. The 4 mod 5 segment is sometimes traversed by Y, and never by Y.
0 1 2 3 4
******
X X neither Y Y
maybe maybe
A 4 mod 5 segment has one or more trailing 4s and at +1 for the next segment they become 0s and increment the lowest non4.
++++
 ...  d  4...4  N == 4 mod 5 X never
++++ Y maybe
++++
 ...  d+1  0...0  N+1 == 0 mod 5 X maybe
++++ Y never
Per the Y rule, a 4 mod 5 segment is traversed when d=2,3. The following segment is then d+1=3,4 as lowest nonzero which in the X rule is nottraversed. Conversely in the Y rule nottraversed when d=0,1 which becomes d+1=1,2 which in the X rule is traversed.
So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are traversed.
XsegPred(X) or YsegPred = 1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,...
=1 at 0,1,3,5,6,8,10,11,13,14,16,18,19,21,23,25,...
SEE ALSO
Math::PlanePath, Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
MathPlanePath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with MathPlanePath. If not, see <http://www.gnu.org/licenses/>.