Math::PlanePath::DragonCurve -- dragon curve
use Math::PlanePath::DragonCurve; my $path = Math::PlanePath::DragonCurve->new; my ($x, $y) = $path->n_to_xy (123);
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 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
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.
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.
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.
arms
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.
arms => 4
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.
$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.
$n
$n < 0
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.
$x,$y
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.
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 0
The 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.
Math::PlanePath, Math::PlanePath::DragonMidpoint
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.