and 1 contributors

# NAME

Math::PlanePath::DragonCurve -- dragon curve

# SYNOPSIS

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

# DESCRIPTION

This is the dragon or paper folding curve by Heighway, Harter, et al,

``````                 9----8    5---4               2
|    |    |   |
10--11/7---6   3---2           1
|            |
17---16   13---12        0---1       <- Y=0
|    |    |
18-19/15-14/22-23                       -1
|    |    |
20---21/25-24                      -2
|
26---27                       -3
|
--32   29---29---28                       -4
|    |
31---30                                 -5

^    ^    ^    ^    ^   ^   ^
-5   -4   -3   -2   -1  X=0  1 ...``````

The curve visits "inside" X,Y points twice. The first of these is X=-2,Y=1 which is N=7 and also N=11. The corners N=6,7,8 and N=10,11,12 have touched, but the path doesn't cross itself. The doubled vertices are all like this, touching but not crossing, and no edges repeating.

The first step N=1 is to the right along the X axis and the path then slowly spirals counter-clockwise and progressively fatter. The end of each replication is N=2^level which is level*45 degrees around,

``````    N       X,Y     angle
----    -----    -----
1      1,0        0
2      1,1       45
4      0,2       90
8     -2,2      135
16     -4,0      180
32     -4,-4     225
...``````

Here's points N=0 to N=2^9=512 with the N=512 end at the "+" mark. It's gone full-circle around to to 45 degrees up again like the initial N=2.

``````                                    * *     * *
* * *   * * *
* * * * * * * * *
* * * * * * * * *
* *   * * * *       * *
* * *   * * * *     + * *
* * * * * *         * *
* * * * * * *
* * * * * * * *
* * * * * *
* * * *
* * * * * * *
* *   * * * * * * * *
* * *   * * * * * * * *
* * * * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * *
* * * *                   * * * * * * * * * * *
* * * * *           * *   * * * *       * * * * *
* * * *   0 *         * * *   * * * *   * * * * * * *
* * * *               * * * * * *       * * * * *
* * *               * * * * * * *       * * * *
* * * *     * *   * * * * * * * *
* * * * * *   * * *   * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * *       * * * * *
* * * * * * *   * * * * * * *
* * * * *       * * * * *
* * * *         * * * *``````

## Paper Folding

The path is called a paper folding curve because it can be generated by thinking of a long strip of paper folded in half repeatedly then unfolded so each crease is a 90 degree angle. The effect is that the curve repeats in successive doublings turned by 90 degrees and reversed. For example the first segment unfolds,

``````                                          2
->   |
unfold         /     |
|      |
|
0-------1                     0-------1``````

Then same again with that L shape, etc,

``````                                 4
|
|
|
3--------2
2                              |
|        unfold          ^     |
|                         \_   |
|                              |
0------1                     0--------1``````

It can be shown that this unfolding doesn't overlap itself, but the corners may touch, such as at the X=-2,Y=1 etc noted above.

## Turns

At each point N the curve always turns either to the left or right, it never goes straight ahead. The bit above the lowest 1 bit in N gives the turn direction. For example at N=11 shown above the curve has just gone downwards from N=11. N=12 is binary 0b1100, the lowest 1 bit is the 0b.1.. and the bit above that is a 1, which means turn to the right. Whereas later at N=18 which has gone downwards from N=17 it's N=18 in binary 0b10010, the lowest 1 is 0b...1., and the bit above that is 0, so turn left.

The bits also give turn after the next by taking the bit above the lowest 0. For example at N=12 the lowest 0 is the least significant bit, and above that is a 0 too, so after going to N=13 the next turn is then to the left to go to N=14. Or for N=18 the lowest 0 is again the least significant bit, but above that is a 1 too, so after going to N=19 the next turn is to the right to go to N=20.

## Arms

The curve fills a quarter of the plane and four copies mesh together perfectly when rotated by 90, 180 and 270 degrees. The `arms` parameter can choose 1 to 4 curve arms, successively advancing.

For example `arms => 4` begins as follows, with N=0,4,8,12,etc being one arm, N=1,5,9,13 the second, N=2,6,10,14 the third and N=3,7,11,15 the fourth.

``````             20 ------ 16
|
9 ------5/12 -----  8       23
|         |         |        |
17 --- 13/6 --- 0/1/2/3 --- 4/15 --- 19
|       |         |         |
21      10 ----- 14/7 ----- 11
|
18 ------ 22``````

With four arms every X,Y point is visited twice (except the origin 0,0 where all four begin) and every edge between the points is traversed once.

# FUNCTIONS

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

`\$path = Math::PlanePath::DragonCurve->new ()`
`\$path = Math::PlanePath::DragonCurve->new (arms => 2)`

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.

The optional `arms` parameter can 1 to 4 copies of the curve, each arm successively advancing.

`\$n = \$path->xy_to_n (\$x,\$y)`

Return the point number for coordinates `\$x,\$y`. If there's nothing at `\$x,\$y` then return `undef`.

The curve visits an `\$x,\$y` twice for various points (all the "inside" points). In the current code the smaller of the two N values is returned. Is that the best way?

`\$n = \$path->n_start()`

Return 0, the first N in the path.

# OEIS

The Dragon curve is in Sloane's Online Encyclopedia of Integer Sequences as turns or a total rotation at each line segment,

``````    http://oeis.org/A005811  (etc)

A005811 -- total rotation, from 0
A014577 -- turn, 0=left, 1=right
A014707 -- turn, 1=left, 0=right
A014709 -- turn, 2=left, 1=right
A014710 -- turn, 1=left, 2=right
A082410 -- turn, 0=left, 1=right with leading 0``````

The four turn sequences differ only in left or right represented as 0 and 1 or 1 and 2.

For reference, A059125 is almost the same as A014577, but differs at some positions.