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 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.
The first segment unfolds, pivoting at the "1",
2 -> | unfold / | ===> | | | 0-------1 0-------1
Then same again with that L shape, pivoting at the "2", and so on.
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.
N = 0b...z100..00 (possibly no trailing 0s) z bit Turn ----- ---- 0 left 1 right
For example 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. Or later N=18 is binary 0b10010, the lowest 1 is 0b...1. and the bit above that is 0, so turn left there.
This can be found with some bit twiddling
$mask = $n ^ -$n; # lowest 1 bit, 000100..00 $z = $n & ($mask << 1); # the bit above it $turn = ($z == 0 ? 'left' : 'right');
The bits also give the turn after next by looking at the bit above the lowest 0.
N = 0b...w011..11 (possibly no trailing 1s) w bit Next Turn ---- --------- 0 left 1 right
For example at N=12=0b1100 the lowest 0 is the least significant bit, and above that is a 0 too, so after going to N=13 the turn there at 13 is to the left. Or for N=18=0b10010 the lowest 0 is again the least significant bit, but above it is a 1, so at N=19 the turn there is to the right.
This too can be found with some bit twiddling, either with a ones-complement to turn it into low ones, or directly as for example
$mask = $n ^ ($n+1); # low bits 000111..11 $z = $n & ($mask + 1); # the solitary bit above it $turn = ($z == 0 ? 'left' : 'right');
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.
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::DragonCurve->new ()
$path = Math::PlanePath::DragonCurve->new (arms => 4)
Create and return a new path object.
The optional arms parameter can make 1 to 4 copies of the curve, each arm successively advancing.
($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.
$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?
The current implementation is a bit slow due to a crude backtracking digits search.
$n = $path->n_start()
Return 0, the first N in the path.
The Dragon curve is in Sloane's Online Encyclopedia of Integer Sequences in various forms,
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 A038189 -- bit above lowest 1, is 0=left,1=right (extra initial 0) A082410 -- reversing complement, is 1=left,0=right (extra initial 0) A091072 -- odd part 4K+1, is N positions of the left turns A126937 -- points numbered like SquareSpiral (N-1, neg Y)
The four turn sequences differ only in having left or right represented as 0 and 1, or 1 and 2, and the extras A038189 and A082410 differ only in beginning with an extra initial 0.
The square numbering A126937 is a Dragon curve going downwards towards negative Y and the spiral numbering starting from N=0 and spiralling upwards towards positive Y. So starting i=0 it can be calculated as
my $dragon = Math::PlanePath::DragonCurve->new; my $square = Math::PlanePath::SquareSpiral->new; my ($x, $y) = $dragon->n_to_xy ($i); my $A126937_of_i = $square->xy_to_n ($x, -$y) - 1;
For reference, "dragon-like" A059125 is almost the same as the turn sequence A014577, but differs at some positions.
Math::PlanePath, Math::PlanePath::DragonRounded, Math::PlanePath::DragonMidpoint, Math::PlanePath::TerdragonCurve, Math::PlanePath::ComplexMinus, Math::PlanePath::ComplexPlus
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012 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.