Math::PlanePath::DekkingCurve -- 5x5 self-similar edge curve
use Math::PlanePath::DekkingCurve; my $path = Math::PlanePath::DekkingCurve->new; my ($x, $y) = $path->n_to_xy (123);
This is an integer version of a 5x5 self-similar curve by Dekking,
10 | 123-124-125-... 86--85 | | | | 9 | 115-116-117 122-121 90--89--88--87 84 | | | | | | 8 | 114-113 118-119-120 91--92--93 82--83 | | | | 7 | 112 107-106 103-102 95--94 81 78--77 | | | | | | | | | | 6 | 111 108 105-104 101 96--97 80--79 76 | | | | | | 5 | 110-109 14--15 100--99--98 39--40 75 66--65 | | | | | | | | 4 | 10--11--12--13 16 35--36--37--38 41 74 71--70 67 64 | | | | | | | | | | 3 | 9---8---7 18--17 34--33--32 43--42 73--72 69--68 63 | | | | | | 2 | 5---6 19 22--23 30--31 44 47--48 55--56--57 62--61 | | | | | | | | | | | | 1 | 4---3 20--21 24 29--28 45--46 49 54--53 58--59--60 | | | | | | Y=0 | 0---1---2 25--26--27 50--51--52 +---------------------------------------------------------------- X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
The base pattern is the N=0 to N=25 section. 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.
The curve segments are edges of squares in a 5x5 arrangement.
+- - -+- - -+- - 14----15 ---+ | | | | v |> | ^ ^ <| | 10----11----12----13- - 16 --+ | v |> | |> ^ ^ | 9-----8-----7 -- 18----17 --+ v | | |> | | ^ |> | ^ +- - 5-----6 - 19 22----23 | <| | <| | <| ^ | <| | +- - 4-----3 20----21 -- 24 | v <| ^ ^ |> | | | 0-----1-----2 -- + -- -+- 25
The little notch marks show which square each edge represents. This is the side the curve 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.
The optional arms parameter can give up to four copies of the curve, each advancing successively. Each copy is in a successive quadrant.
arms
arms => 3 | 67-70-73 42-45 5 | | | 43-46-49 64-61 30-33-36-39 48 4 | | | | | 40-37 52-55-58 27-24-21 54-51 3 | | | 34 19-16 7--4 15-18 57 66-69 2 | | | | | | | | | 31 22 13-10 1 12--9 60-63 72 1 | | | | ...--74 28-25 5--2 0--3--6 75-... <-- Y=0 | | 71 62-59 8-11 -1 | | | | 68-65 56 17-14 -2 | | 50-53 20-23-26 -3 | | 47 38-35-32-29 -4 | | 44-41 -5 ^ ... -5 -4 -3 -2 -1 X=0 1 2 3 4 5 ...
The origin is N=0 only and is on the first arm. The second and subsequent arms begin 1,2,etc. The curves interleave perfectly on the Y axis where the first and second arms meet, and the same on the other axes. The result is that 4 arms fill the plane visiting each integer X,Y exactly once and not touching.
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.
$n
$n < 0
($n_lo, $n_hi) = $path->level_to_n_range($level)
Return (0, 25**$level), or for multiple arms return (0, $arms * 25**$level).
(0, 25**$level)
(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 + (arms-1)*25^level = arms*25^level + 1 many points starting from 0.
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 not-traversed if low digit 2 or 3 or 4 when low digit == 0 traversed if lowest non-zero 1 or 2 not-traversed if lowest non-zero 3 or 4
In the samples the segments at X=1, X=6 and X=11 segments traversed are the low digit 1 rule. Their preceding X=5 and X=10 segments are low digit==0 and the lowest non-zero 1 or 2 (respectively). At X=15 however the lowest non-zero is 3 and so not-traversed.
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 non-zero 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 sub-parts 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 the start is S. 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 non-zero 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 not-traversed.
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 <--- 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| /0 1 | 2\ |3,4 base 5 digits of X | / | | \ | high to low +-> | v | | v | <-+ +-- West 2---------> East --+ start in South, 0,4 | ^ | | ^ | 2 segment traversed | \ | | / | if end in South 1| \4 | 3 2/ |0,1 | \ v | / | +---> 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 -------> not-traversed 0|^ ++
In state m1 a 0 digit loops back to m1 and finds the lowest non-zero. Digit 2 result differs according to whether there are any low 0s.
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 not-traversed if lowest digit 0 or 1 or 2 when lowest digit == 4 traversed if lowest non-4 is 2 or 3 not-traversed if lowest non-4 is 0 or 1
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 since they differ only in digit 0 destination N or W and both as final state are not-traversed.
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.
For multiple arms a copy of the curve is rotated +90 degrees so that the X axis of the rotated copy is on the Y axis. The segments do not overlap nor does the curve touch.
This can be 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 never Y Y maybe always always maybe
A 4 mod 5 segment has one or more trailing 4s and +1 for the next segment makes them 0s and increments the lowest non-4. This means that lowest non-4 digit is traversed 2,3 and not 0,1 becomes 3,4 and 0,1 and for the X axis rule are not-traversed or traversed respectively. So exactly one of two consecutive 4 mod 5 and 0 mod 5 segments are traversed.
Math::PlanePath, Math::PlanePath::DekkingCentres, Math::PlanePath::CincoCurve, Math::PlanePath::PeanoCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012, 2013, 2014, 2015 Kevin Ryde
This file is part of Math-PlanePath.
Math-PlanePath 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.
Math-PlanePath 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 Math-PlanePath. If not, see <http://www.gnu.org/licenses/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.