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,
98 54 2
   
1011/76 32 1
 
1716 1312 01 < Y=0
  
1819/1514/2223 1
  
2021/2524 2

2627 3

32 292928 4
 
3130 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 counterclockwise 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 fullcircle 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 / 
 

01 01
Then same again with that L shape, etc,
4



32
2 
 unfold ^ 
 \_ 
 
01 01
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 returnundef
.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/mathplanepath/index.html
LICENSE
Copyright 2011 Kevin Ryde
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.