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

NAME

       Math::PlanePath::R5DragonMidpoint -- R5 dragon curve midpoints

SYNOPSIS

        use Math::PlanePath::R5DragonMidpoint;
        my $path = Math::PlanePath::R5DragonMidpoint->new;
        my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

       This is midpoints of the R5 dragon curve by Jorg Arndt,

                                              31--30                       11
                                               |   |
                                              32  29                       10
                                               |   |
                      51--50          35--34--33  28--27--26                9
                       |   |           |                   |
                      52  49          36--37--38  23--24--25                8
                       |   |                   |   |
              55--54--53  48--47--46  41--40--39  22                        7
               |                   |   |           |
              56--57--58  63--64  45  42  19--20--21                        6
                       |   |   |   |   |   |
              81--80  59  62  65  44--43  18--17--16  11--10                5
               |   |   |   |   |                   |   |   |
              82  79  60--61  66--67--68          15  12   9                4
               |   |                   |           |   |   |
           ..-83  78--77--76  71--70--69          14--13   8-- 7-- 6        3
                           |   |                                   |
                          75  72                           3-- 4-- 5        2
                           |   |                           |
                          74--73                           2                1
                                                           |
                                                       0-- 1           <- Y=0

               ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
             -10  -9  -8  -7  -6  -5  -4  -3  -2  -1  X=0  1   2   3

       The points are the middle of each edge of the "R5DragonCurve", rotated -45 degrees, shrunk
       by sqrt(2). and shifted to the origin.

                     *--11--*     *--7--*     R5DragonCurve
                     |      |     |     |     and its midpoints
                    12     10     8     6
                     |      |     |     |
              *--17--*--13--*--9--*--5--*
              |      |      |     |
             18     16     14     4
              |      |      |     |
           ..-*      *--15--*     *--3--*
                                        |
                                        2
                                        |
                                  +--1--*

   Arms
       Multiple copies of the curve can be selected, each advancing successively.  Like the main
       "R5DragonCurve" this midpoint curve covers 1/4 of the plane and 4 arms rotated by 0, 90,
       180, 270 degrees mesh together perfectly.  With 4 arms all integer X,Y points are visited.

       "arms => 4" begins as follows.  N=0,4,8,12,16,etc is the first arm (the same shape as the
       plain curve above), then N=1,5,9,13,17 the second, N=2,6,10,14 the third, etc.

           arms=>4     76--80-...                                6
                        |
                       72--68--64  44--40                        5
                                |   |   |
                       25--21  60  48  36                        4
                        |   |   |   |   |
                       29  17  56--52  32--28--24  75--79        3
                        |   |                   |   |   |
               41--37--33  13-- 9-- 5  12--16--20  71  83        2
                |                   |   |           |   |
               45--49--53   6-- 2   1   8  59--63--67  ...       1
                        |   |           |   |
           ... 65--61--57  10   3   0-- 4  55--51--47        <- Y=0
            |   |           |   |                   |
           81  69  22--18--14   7--11--15  35--39--43           -1
            |   |   |                   |   |
           77--73  26--30--34  54--58  19  31                   -2
                            |   |   |   |   |
                           38  50  62  23--27                   -3
                            |   |   |
                           42--46  66--70--74                   -4
                                            |
                                   ...-82--78                   -5

            ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
           -6  -5  -4  -3  -2  -1  X=0  1   2   3   4   5

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

       "$path = Math::PlanePath::R5DragonMidpoint->new ()"
           Create and return a new path object.

       "($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.

           Fractional positions give an X,Y position along a straight line between the integer
           positions.

       "$n = $path->n_start()"
           Return 0, the first N in the path.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, 5**$level - 1)", or for multiple arms return "(0, $arms * 5**$level - 1)".

           There are 5^level segments comprising the curve, or arms*5^level when multiple arms,
           numbered starting from 0.

FORMULAS

   X,Y to N
       An X,Y point can be turned into N by dividing out digits of a complex base 1+2i.  At each
       step the low base-5 digit is formed from X,Y and an adjustment applied to move X,Y to a
       multiple of 1+2i ready to divide out.

       A 10x10 table is used for the digit and adjustments, indexed by Xmod10 and Ymod10.
       There's probably an a*X+b*Y mod 5 or mod 20 for a smaller table.  But in any case once the
       adjustment is found the result is

           Ndigit = digit_table[X mod 10, Y mod 10]  # low to high
           Xm = X + Xadj_table [X mod 10, Y mod 10]
           Ym = Y + Yadj_table [X mod 10, Y mod 10]

           new X,Y = (Xm,Ym) / (1+2i)
                   = (Xm,Ym) * (1-2i) / 5
                   = ((Xm+2*Ym)/5, (Ym-2*Xm)/5)

       These X,Y reductions eventually reach one of the starting points for the four arms

           X,Y endpoint   Arm        +---+---+
           ------------   ---        | 2 | 1 |  Y=1
               0, 0        0         +---+---+
               0, 1        1         | 3 | 0 |  Y=0
              -1, 1        2         +---+---+
              -1, 0        3         X=-1 X=0

       For arms 1 and 3 the digits must be flipped 4-digit, so 0,1,2,3,4 -> 4,3,2,1,0.  The arm
       number and hence whether this flip is needed is not known until reaching the endpoint.

           if arm odd
           then  N = 5^numdigits - 1 - N

       If only some of the arms are of interest then reaching one of the other arm numbers means
       the original X,Y was outside the desired curve.

SEE ALSO

       Math::PlanePath, Math::PlanePath::R5DragonCurve

       Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonMidpoint

HOME PAGE

       <http://user42.tuxfamily.org/math-planepath/index.html>

LICENSE

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