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 paper folding curve by Heighway, Harter, et al, per 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 of each segment are numbered from 0,
+--8--+ +--4--+ | | | | 9 7 5 3 | | | | +-10--+--6--+ +--2--+ | | 11 1 | | +-12--+ *--0--+ | ...
These midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc. For this DragonMidpoint path they're turned clockwise 45 degrees and shrunk by sqrt(2) to be integer X,Y values 1 apart and initial direction to the right.
DragonMidpoint
The midpoints are distinct X,Y positions because the dragon curve traverses each edge only once.
The dragon curve is self-similar in 2^level sections due to its unfolding. This can be seen in the midpoints too as for example above N=0 to N=16 is the same shape as N=16 to N=32, with the latter rotated 90 degrees and in reverse.
Since the dragon curve always turns left or right, never straight ahead or reverse, the segments are alternately horizontal and vertical. With the rotate -45 degrees for the midpoints done here this means alternately "opposite diagonal" segment and "leading diagonal" segment. They fall on X,Y alternately even or odd. So the original dragon curve can be recovered by choosing either a leading or opposite diagonal segment according to either X,Y even/odd or N even/odd.
DragonMidpoint dragon segment -------------- ----------------- "even" N==0 mod 2 opposite diagonal which is X+Y==0 mod 2 too "odd" N==1 mod 2 leading diagonal which is X+Y==1 mod 2 too / 3 0 at X=0,Y=0 "even", opposite slope / 1 at X=1,Y=0 "odd", leading slope \ etc 2 \ \ / 0 1 \ /
Like the DragonCurve 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.
DragonCurve
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 repeating in 4x4 blocks.
+---+---+---+-+-+---+-+-+---+ | | | | | | | | | | | +---+ | +---+ | +---+ | +---+ | | | |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 shown, and also for the rotated copies per "Arms" above.
Taking pairs N=2k+1 and N=2k+2, being odd N and its successor, gives a regular pattern too, but this time repeating in blocks of 16x16.
|||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--||| |||--||||||--||--||--||||||--||||||--||||||--||||||--||||||--||| -||------||------||------||------||------||------||------||----- -||------||------||------||------||------||------||------||----- |||--||||||||||||||--||||||||||||||--||||||||||||||--||||||||||| |||--||||||||||||||--||||||||||||||--||||||||||||||--||||||||||| -----||------||------||------||------||------||------||------||- -----||------||------||------||------||------||------||------||- -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||- -||--||--||--||--||--||||||--||--||--||--||--||--||--||||||--||- -||------||------||------||------||------||------||------||----- -||------||------||------||------||------||------||------||----- |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--||| |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--||| -----||------||------||------||------||------||------||------||- -----||------||------||------||------||------||------||------||- |||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--||| |||--||||||--||--||--||||||--|| ||--||||||--||--||--||||||--||| -||------||------||------||------||------||------||------||----- -||------||------||------||------||------||------||------||----- |||--||||||||||||||--||||||||||||||--||||||||||||||--||||||||||| |||--||||||||||||||--||||||||||||||--||||||||||||||--||||||||||| -----||------||------||------||------||------||------||------||- -----||------||------||------||------||------||------||------||- -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||- -||--||||||--||--||--||--||--||--||--||||||--||--||--||--||--||- -||------||------||------||------||------||------||------||----- -||------||------||------||------||------||------||------||----- |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--||| |||||||||||--||||||||||||||--||||||||||||||--||||||||||||||--||| -----||------||------||------||------||------||------||------||- -----||------||------||------||------||------||------||------||-
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 multiplied by i+1. The adjustment pattern is a little like the pair tiling shown above, but for some pairs both the N=2k and N=2k+1 positions must move, it's not enough just to shift 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 per "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 and Ym-Xm are both even Nbit = Xadj xor Yadj # new low bit of N new N = N + (Nbit << count++)
The X,Y reduction stops at one of the 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 and 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 abs(dY) of n-1 to n, so 0=horizontal,1=vertical (extra initial 0) A077860 Y at N=2^k, being Re(-(i+1)^k + i-1)
The midpoint curve is vertical when the DragonCurve has a vertical followed by a left turn, or 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 "Turn" in Math::PlanePath::DragonCurve. So
abs(dY) = lowbit(N) XOR bit-above-lowest-zero(N)
The n of A073089 is offset by 2 from the N numbering of the path here, so n=N+2. The initial value at n=1 in A073089 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 segments. The recursion a(8n+1)=a(4n+1) works to reduce an N=0b.zz111 to 0b..zz11 in order to bring a lowest 0 into range of the mod-16 conditions. n=1 mod 8 corresponds to path N=7 mod 8. In terms of path N it would be expressed as stripping low 1 bits down to at most 2 of them. In terms of OEIS n it's a strip of zeros above a low 1 bit, ie. n=0b...00001 -> 0b...01.
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded
Math::PlanePath::AlternatePaperMidpoint, Math::PlanePath::R5DragonMidpoint, Math::PlanePath::TerdragonMidpoint
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2011, 2012, 2013 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.