++ed by:
Kevin Ryde
and 1 contributors

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

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

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