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 the midpoint of each segment of the dragon or paper folding curve by Heighway, Harter, et al (see Math::PlanePath::DragonCurve).
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 begins as follows and the midpoints are each "*",
+--*--+ +--*--+ | | | | * * * * | | | | +--*--+--*--+ +--*--+ | | * * | | +--*--+ o--*--+ | ...
These midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc. For this DragonMidpoint 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 dragon curve is self-similar in 2^level sections due to its unfolding. This can be seen in the midpoints as for example above N=0 to N=16 is the same shape as N=32 to N=16, the latter part rotated and in reverse.
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 the plain curve 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, because four arms of the DragonCurve traverse every edge exactly once.
Taking pairs of points N=2k and N=2k+1 gives little rectangles with the following tiling of the plane.
+---+---+---+-+-+---+-+-+---+ | | | | | | | | | | | +---+ | +---+ | +---+ | +---+ | | | |9 8| | | | | | | +-+-+---+-+-+-+-+-+-+-+-+-+-+ | | | | |7| | | | | | | | | +---+ | +---+ | +---+ | | | | | | |6|5 4| | | | | | +---+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | |3| | | | | +---+ | +---+ | +---+ | +---+ | | | | | |2| | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | |0 1| | | | | | <- Y=0 | | +---+ | +---+ | +---+ | | | | | | | | | | | | | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | | | | | | | | | | +---+ | +---+ | +---+ | +---+ | | | | | | | | | | | +---+-+-+---+-+-+---+-+-+---+ ^ X=0
The pairs follow this pattern both for the main curve N=0 etc as shown, and also for the rotated copies per "Arms" above.
See "FUNCTIONS" in Math::PlanePath for 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 is turned into N by dividing out digits of a complex base i+1. This base is per the doubling of the DragonCurve at each level. In midpoint coordinates an adjustment subtracting 0 or 1 must be applied to move an X,Y for N=2k or N=2k+1 to the point where dividing out i+1 gives the N=k position.
The adjustment is in a repeating pattern of 4x4 blocks. Points N=2k and N=2k+1 both move to the same place corresponding to N=k times i+1. The pattern is related to the pair tiling shown above, but for some pairs both the N=2k and N=2k+1 positions must move, it's not just a matter of shifting the N=2k+1 to the N=2k.
Xadj Yadj Ymod4 Ymod4 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 0 | 0 1 1 0 0 | 0 0 1 1 +-------- +-------- 0 1 2 3 0 1 2 3 Xmod4 Xmod4
The same tables work for both the main curve and for the rotated copies shown in "Arms" above.
Xm = X - Xadj (X mod 4, Y mod 4) Ym = Y - Yadj (X mod 4, Y mod 4) new X,Y = (Xm+i*Ym) / (i+1) = (Xm+i*Ym) * (1-i)/2 = (Xm+Ym)/2, (Ym-Xm)/2 # Xm+Ym, Ym-Xm are even Nbit = Xadj xor Yadj new N = N + (Nbit << count++) # new low bit
The X,Y reduction stops at one of the four start points for the four arms
X,Y endpoint Arm 0, 0 0 0, 1 1 -1, 1 2 -1, 0 3
For arms 1 and 3 the N bits must be flipped 0<->1. The arm number an hence whether this flip is needed is not known until reaching the endpoint.
For bignum calculations there's no need to apply the "/2" shift in newX=(Xm+Ym)/2 and newY=(Ym-Xm)/2. Instead keep a bit position which is the logical low end and pick out two bits from there for the Xadj,Yadj lookup. A whole word can be dropped when the bit position becomes a multiple of 32 or 64 or whatever.
The DragonMidpoint is in Sloane's Online Encyclopedia of Integer Sequences as
http://oeis.org/A073089 A073089 -- segments 0=horizontal, 1=vertical (extra initial 0)
The midpoint curve is vertical when the DragonCurve has a vertical followed by a left turn or a horizontal followed by a right turn. DragonCurve verticals are whenever N is odd, and the turn is the bit above the lowest 0 in N, as described in "Turns" in Math::PlanePath::DragonCurve.
Note the n of A073089 is n=N+2 in the numbering of the DragonMidpoint here, and its initial value at n=1 has no corresponding N (it would be N=-1).
The mod-16 definitions in A073089 express combinations of N odd/even and bit-above-low-0 which are the vertical midpoint segment. The recursion a(8n+1)=a(4n+1) works to reduce an N=0b.zz111 to 0b..zz11 in order to bring the bit above the lowest 0 into range of the mod-16 conditions. n=1 mod 8 corresponds to N=7 mod 8. In terms of N it could be expressed as stripping low 1 bits down to at most 2 of them. In terms of n it's a strip of zeros above a least significatn 1 bit, ie. n=0b...00001 -> 0b...01.
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.