Provided by: libmath-planepath-perl_125-1_all bug

NAME

       Math::PlanePath::DekkingCurve -- 5x5 self-similar 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 self-similar curve from

           F. M. Dekking, "Recurrent Sets", Advances in Mathematics, volume 44, 1982, pages
           79-104, section 4.9 "Gosper-Type Curves"

       This is a horizontal mirror image of the E-curve of McKenna (1978).

       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 |             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 curve segments correspond to 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 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 anti-clockwise 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                |
                             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 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 + (arms-1)*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
           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

           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 non-zero 1 or 2
       (respectively).  At X=15 however the lowest non-zero is 3 and so not-traversed 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 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 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 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  <--- 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 -------> not-traversed
                             0| ^
                              +-+

       In state m1 a 0 digit loops back to m1 so finds the lowest non-zero.  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
           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

           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 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.

   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 non-4.

           +--------+-----+-------+
           |  ...   |  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 non-zero which in the X rule is not-traversed.  Conversely in the Y rule
       not-traversed 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/math-planepath/index.html>

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 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/>.