Math::PlanePath::DragonMidpoint -- dragon curve midpoints
use Math::PlanePath::DragonMidpoint; my $path = Math::PlanePath::DragonMidpoint->new; my ($x, $y) = $path->n_to_xy (123);
This is an integer version of the dragon or paper folding curve by Heighway, Harter, et al, following the midpoint of each edge of the curve segments.
17--16 9---8 5 | | | | 18 15 10 7 4 | | | | 19 14--13--12--11 6---5---4 3 | | 20--21--22 3 2 | | 33--32 25--24--23 2 1 | | | | 34 31 26 0---1 <- Y=0 | | | 35 30--29--28--27 -1 | 36--37--38 43--44--45--46 -2 | | | 39 42 49--48--47 -3 | | | 40--41 50 -4 | 51 -5 | 52--53--54 -6 | ..--64 57--56--55 -7 | | 63 58 -8 | | 62--61--60--59 -9 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X=0 1
The dragon curve itself begins as follows and the edge midpoints at each "*",
--*-- --*-- | | | | * * * * | | | | --*--+--*-- --*-- | | * * | | --*--+ --*-- | ...
The midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc. Those positions can be had from the DragonCurve module by asking for N=0.5, 1.5, 2.5, etc. For this DragonMidpoint curve they're turned clockwise 45 degrees and shrunk by sqrt(2) to be integer X,Y values 1 apart.
Because the dragon curve traverses each edge only once, all the midpoints are distinct X,Y positions.
The midpoints fill 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 the first arm (the same as above), N=1,5,9,13 the second, N=2,6,10,14 the third and N=3,7,11,15 the fourth.
arms => 4
...-107-103 83--79--75--71 6 | | | 68--64 36--32 99 87 59--63--67 5 | | | | | | | 72 60 40 28 95--91 55 4 | | | | | 76 56--52--48--44 24--20--16 51 3 | | | 80--84--88 17--13---9---5 12 47--43--39 ... 2 | | | | | | 100--96--92 21 6---2 1 8 27--31--35 106 1 | | | | | | 104 33--29--25 10 3 0---4 23 94--98-102 <- Y=0 | | | | | | ... 37--41--45 14 7--11--15--19 90--86--82 -1 | | | 49 18--22--26 46--50--54--58 78 -2 | | | | | 53 89--93 30 42 62 74 -3 | | | | | | | 65--61--57 85 97 34--38 66--70 -4 | | | 69--73--77--81 101-105-... -5 ^ -6 -5 -4 -3 -2 -1 X=0 1 2 3 4 5
With four arms like this every X,Y point is visited exactly once, corresponding to the way four copies of the dragon curve traversing each edge exactly once.
See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.
$path = Math::PlanePath::DragonMidpoint->new ()
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.
$n = $path->n_start()
Return 0, the first N in the path.
An X,Y point can be turned into N by dividing out digits of a base complex i+1. An adjustment is applied at each step to put X,Y onto a multiple of i+1 and this gives a bit for N, from low to high.
The adjustment from X mod 4 and Y mod 4 is per the following tables. (Arising essentially because at successive levels of greater detail segments cannot cross and don't go straight ahead.)
Xadj Yadj 3 | 0 1 1 0 3 | 1 1 0 0 2 | 1 0 0 1 2 | 1 1 0 0 1 | 1 0 0 1 1 | 0 0 1 1 Y=0 | 0 1 1 0 Y=0 | 0 0 1 1 +-------- +-------- X=0 1 2 3 X=0 1 2 3
So
Xm = X + Xadj(X%4,Y%4) Ym = Y + Yadj(X%4,Y%4) new X,Y = (Xm+i*Ym) / (i+1) = (Xm+i*Ym) * (1-i)/2 = (Xm+Ym)/2, (Ym-Xm)/2 Nbit = Xadj xor Yadj new N = N + Nbit << count++
Each Nbit is a bit for N, from low to high. The X,Y reduction stops on reaching one of the four points X=0,-1 and Y=0,1 which are the N=0,1,2,3 points of the 4-arms shown above. That final N is thus the curve arm, eg. X=0,Y=0 is the first arm. For endpoints X=0,Y=1 and X=-1,Y=0 the N bits must be flipped.
The table represents moving X,Y which is a curve midpoint K to K+1 to the midpoint of either K to K+2 or K+1 to K+3, whichever of those two are even. In terms of N it moves to int(N/2), and Nbit the remainder, ie. N=2*newN+Nbit.
There's probably no need for the "/2" dividing out for the new X,Y at each step, if the Xadj,Yadj lookup were taken at, and applied to, a suitably higher bit position each time.
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::TerdragonMidpoint
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.