++ed by:
EGOR BHANN

2 PAUSE users

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

SEE ALSO

Math::PlanePath, Math::PlanePath::DragonRounded, Math::PlanePath::DragonMidpoint, Math::PlanePath::ComplexMinus

HOME PAGE

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

LICENSE

Copyright 2011 Kevin Ryde

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