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-------1Then same again with that L shape, etc,
4
|
|
|
3--------2
2 |
| unfold ^ |
| \_ |
| |
0------1 0--------1It 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 ------ 22With 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
$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
$non the path. Points begin at 0 and if$n < 0then the return is an empty list.Fractional positions give an X,Y position along a straight line between the integer positions.
The optional
armsparameter 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,$ythen returnundef.The curve visits an
$x,$ytwice 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, 0 up
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, same as A014577 plus leading 0The four turn sequences differ only in being 0 and 1 or 1 and 2, and which is treated as left or right.
For reference, A059125 is almost the same as A014577, but differs at some positions.
SEE ALSO
Math::PlanePath, Math::PlanePath::DragonMidpoint
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/>.