NAME
Math::PlanePath::DragonMidpoint -- dragon curve midpoints
SYNOPSIS
use Math::PlanePath::DragonMidpoint;
my $path = Math::PlanePath::DragonMidpoint->new;
my ($x, $y) = $path->n_to_xy (123);DESCRIPTION
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 1The 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.
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, the latter rotated 90 degrees and in reverse.
Arms
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.
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.
...-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 5With four arms like this every X,Y point is visited exactly once, because four arms of the DragonCurve traverse every edge exactly once.
Tiling
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=0The pairs follow this pattern both for the main curve N=0 etc shown, and also for the rotated copies per "Arms" above.
FUNCTIONS
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
$non the path. Points begin at 0 and if$n < 0then the return is an empty list.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.
FORMULAS
X,Y to N
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 adjustment pattern is related to the pair tiling shown above, except 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 Xmod4The 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, Ym-Xm are even
Nbit = Xadj xor Yadj
new N = N + (Nbit << count++) # new low bitThe 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 3For 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.
OEIS
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.
The n of A073089 is offset by 2 from the N numbering of the DragonMidpoint here, ie. n=N+2. The A073089 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 segments. The recursion a(8n+1)=a(4n+1) works to reduce an N=0b.zz111 to 0b..zz11 in order to bring a 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 low 1 bit, ie. n=0b...00001 -> 0b...01.
SEE ALSO
Math::PlanePath, Math::PlanePath::DragonCurve,
Math::PlanePath::AlternatePaperMidpoint, Math::PlanePath::R5DragonMidpoint, Math::PlanePath::TerdragonMidpoint
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
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/>.