.\" Automatically generated by Pod::Man 2.28 (Pod::Simple 3.28) .\" .\" Standard preamble: .\" ======================================================================== .de Sp \" Vertical space (when we can't use .PP) .if t .sp .5v .if n .sp .. .de Vb \" Begin verbatim text .ft CW .nf .ne \\$1 .. .de Ve \" End verbatim text .ft R .fi .. .\" Set up some character translations and predefined strings. \*(-- will .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left .\" double quote, and \*(R" will give a right double quote. \*(C+ will .\" give a nicer C++. Capital omega is used to do unbreakable dashes and .\" therefore won't be available. \*(C` and \*(C' expand to `' in nroff, .\" nothing in troff, for use with C<>. .tr \(*W- .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p' .ie n \{\ . ds -- \(*W- . ds PI pi . if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch . if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch . ds L" "" . ds R" "" . ds C` "" . ds C' "" 'br\} .el\{\ . ds -- \|\(em\| . ds PI \(*p . ds L" `` . ds R" '' . ds C` . ds C' 'br\} .\" .\" Escape single quotes in literal strings from groff's Unicode transform. .ie \n(.g .ds Aq \(aq .el .ds Aq ' .\" .\" If the F register is turned on, we'll generate index entries on stderr for .\" titles (.TH), headers (.SH), subsections (.SS), items (.Ip), and index .\" entries marked with X<> in POD. Of course, you'll have to process the .\" output yourself in some meaningful fashion. .\" .\" Avoid warning from groff about undefined register 'F'. .de IX .. .nr rF 0 .if \n(.g .if rF .nr rF 1 .if (\n(rF:(\n(.g==0)) \{ . if \nF \{ . de IX . tm Index:\\$1\t\\n%\t"\\$2" .. . if !\nF==2 \{ . nr % 0 . nr F 2 . \} . \} .\} .rr rF .\" .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2). .\" Fear. Run. Save yourself. No user-serviceable parts. . \" fudge factors for nroff and troff .if n \{\ . ds #H 0 . ds #V .8m . ds #F .3m . ds #[ \f1 . ds #] \fP .\} .if t \{\ . ds #H ((1u-(\\\\n(.fu%2u))*.13m) . ds #V .6m . ds #F 0 . ds #[ \& . ds #] \& .\} . \" simple accents for nroff and troff .if n \{\ . ds ' \& . ds ` \& . ds ^ \& . ds , \& . ds ~ ~ . ds / .\} .if t \{\ . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u" . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u' . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u' . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u' . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u' . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u' .\} . \" troff and (daisy-wheel) nroff accents .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V' .ds 8 \h'\*(#H'\(*b\h'-\*(#H' .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#] .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H' .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u' .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#] .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#] .ds ae a\h'-(\w'a'u*4/10)'e .ds Ae A\h'-(\w'A'u*4/10)'E . \" corrections for vroff .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u' .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u' . \" for low resolution devices (crt and lpr) .if \n(.H>23 .if \n(.V>19 \ \{\ . ds : e . ds 8 ss . ds o a . ds d- d\h'-1'\(ga . ds D- D\h'-1'\(hy . ds th \o'bp' . ds Th \o'LP' . ds ae ae . ds Ae AE .\} .rm #[ #] #H #V #F C .\" ======================================================================== .\" .IX Title "Math::PlanePath::DragonMidpoint 3pm" .TH Math::PlanePath::DragonMidpoint 3pm "2014-08-27" "perl v5.20.1" "User Contributed Perl Documentation" .\" For nroff, turn off justification. Always turn off hyphenation; it makes .\" way too many mistakes in technical documents. .if n .ad l .nh .SH "NAME" Math::PlanePath::DragonMidpoint \-\- dragon curve midpoints .SH "SYNOPSIS" .IX Header "SYNOPSIS" .Vb 3 \& use Math::PlanePath::DragonMidpoint; \& my $path = Math::PlanePath::DragonMidpoint\->new; \& my ($x, $y) = $path\->n_to_xy (123); .Ve .SH "DESCRIPTION" .IX Header "DESCRIPTION" This is the midpoint of each segment of the dragon curve by Heighway, Harter, et al, per Math::PlanePath::DragonCurve. .PP .Vb 10 \& 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 .Ve .PP The dragon curve begins as follows. The midpoints of each segment are numbered starting from 0, .PP .Vb 11 \& +\-\-8\-\-+ +\-\-4\-\-+ \& | | | | \& 9 7 5 3 \& | | | | | \& +\-10\-\-+\-\-6\-\-+ +\-\-2\-\-+ rotate 45 degrees | \& | | v \& 11 1 \& | | \& +\-12\-\-+ *\-\-0\-\-+ * = Origin \& | \& ... .Ve .PP These midpoints are on fractions X=0.5,Y=0, X=1,Y=0.5, etc. For this \&\f(CW\*(C`DragonMidpoint\*(C'\fR path they're turned clockwise 45 degrees and shrunk by \&\fIsqrt\fR\|(2) to be integer X,Y values a unit apart and initial direction to the right. .PP The midpoints are distinct X,Y positions because the dragon curve traverses each edge only once. .PP 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. .SS "Arms" .IX Subsection "Arms" Like the \f(CW\*(C`DragonCurve\*(C'\fR the midpoints fill a quarter of the plane and four copies mesh together perfectly when rotated by 90, 180 and 270 degrees. The \&\f(CW\*(C`arms\*(C'\fR parameter can choose 1 to 4 curve arms, successively advancing. .PP For example \f(CW\*(C`arms => 4\*(C'\fR 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. .PP .Vb 1 \& 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 .Ve .PP With four arms like this every X,Y point is visited exactly once, because four arms of the \f(CW\*(C`DragonCurve\*(C'\fR traverse every edge exactly once. .SS "Tiling" .IX Subsection "Tiling" Taking pairs of adjacent points N=2k and N=2k+1 gives little rectangles with the following tiling of the plane repeating in 4x4 blocks. .PP .Vb 10 \& +\-\-\-+\-\-\-+\-\-\-+\-+\-+\-\-\-+\-+\-+\-\-\-+ \& | | | | | | | | | | | \& +\-\-\-+ | +\-\-\-+ | +\-\-\-+ | +\-\-\-+ \& | | | |9 8| | | | | | | \& +\-+\-+\-\-\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+ \& | | | | |7| | | | | | | \& | | +\-\-\-+ | +\-\-\-+ | +\-\-\-+ | | \& | | | | |6|5 4| | | | | | \& +\-\-\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+ \& | | | | | |3| | | | | \& +\-\-\-+ | +\-\-\-+ | +\-\-\-+ | +\-\-\-+ \& | | | | | |2| | | | | \& +\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+ \& | | | | | |0 1| | | | | | <\- Y=0 \& | | +\-\-\-+ | +\-\-\-+ | +\-\-\-+ | | \& | | | | | | | | | | | | \& +\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+\-+ \& | | | | | | | | | | | \& +\-\-\-+ | +\-\-\-+ | +\-\-\-+ | +\-\-\-+ \& | | | | | | | | | | | \& +\-\-\-+\-+\-+\-\-\-+\-+\-+\-\-\-+\-+\-+\-\-\-+ \& ^ \& X=0 .Ve .PP The pairs follow this pattern both for the main curve N=0 etc shown, and also for the rotated copies per \*(L"Arms\*(R" above. This tiling is in the tilingsearch database as .Sp .RS 4 .RE .PP Taking pairs N=2k+1 and N=2k+2, being each odd N and its successor, gives a regular pattern too, but this time repeating in blocks of 16x16. .PP .Vb 10 \& |||\-\-||||||\-\-||\-\-||\-\-||||||\-\-||||||\-\-||||||\-\-||||||\-\-||||||\-\-||| \& |||\-\-||||||\-\-||\-\-||\-\-||||||\-\-||||||\-\-||||||\-\-||||||\-\-||||||\-\-||| \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& |||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||| \& |||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||| \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\- \& \-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& |||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||| \& |||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||| \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& |||\-\-||||||\-\-||\-\-||\-\-||||||\-\-|| ||\-\-||||||\-\-||\-\-||\-\-||||||\-\-||| \& |||\-\-||||||\-\-||\-\-||\-\-||||||\-\-|| ||\-\-||||||\-\-||\-\-||\-\-||||||\-\-||| \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& |||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||| \& |||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||| \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\- \& \-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||\-\-||||||\-\-||\-\-||\-\-||\-\-||\-\-||\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& \-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\- \& |||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||| \& |||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||||||||||||||\-\-||| \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- \& \-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\-\-\-\-\-\-||\- .Ve .SS "Curve from Midpoints" .IX Subsection "Curve from Midpoints" Since the dragon curve always turns left or right, never straight ahead or reverse, its segments are alternately horizontal and vertical. Rotated \-45 degrees for the midpoints here this means alternately \*(L"opposite diagonal\*(R" and \*(L"leading diagonal\*(R". They fall on X,Y alternately even or odd. So the original dragon curve can be recovered from the midpoints by choosing leading diagonal or opposite diagonal segment according to X,Y even or odd, which is the same as N even or odd. .PP .Vb 4 \& 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 diagonal \& / 1 at X=1,Y=0 "odd", leading diagonal \& \e etc \& 2 \& \e \& \e / \& 0 1 \& \e / .Ve .SH "FUNCTIONS" .IX Header "FUNCTIONS" See \*(L"\s-1FUNCTIONS\*(R"\s0 in Math::PlanePath for behaviour common to all path classes. .ie n .IP """$path = Math::PlanePath::DragonMidpoint\->new ()""" 4 .el .IP "\f(CW$path = Math::PlanePath::DragonMidpoint\->new ()\fR" 4 .IX Item "$path = Math::PlanePath::DragonMidpoint->new ()" Create and return a new path object. .ie n .IP """($x,$y) = $path\->n_to_xy ($n)""" 4 .el .IP "\f(CW($x,$y) = $path\->n_to_xy ($n)\fR" 4 .IX Item "($x,$y) = $path->n_to_xy ($n)" Return the X,Y coordinates of point number \f(CW$n\fR on the path. Points begin at 0 and if \f(CW\*(C`$n < 0\*(C'\fR then the return is an empty list. .Sp Fractional positions give an X,Y position along a straight line between the integer positions. .ie n .IP """$n = $path\->n_start()""" 4 .el .IP "\f(CW$n = $path\->n_start()\fR" 4 .IX Item "$n = $path->n_start()" Return 0, the first N in the path. .SS "Level Methods" .IX Subsection "Level Methods" .ie n .IP """($n_lo, $n_hi) = $path\->level_to_n_range($level)""" 4 .el .IP "\f(CW($n_lo, $n_hi) = $path\->level_to_n_range($level)\fR" 4 .IX Item "($n_lo, $n_hi) = $path->level_to_n_range($level)" Return \f(CW\*(C`(0, 2**$level \- 1)\*(C'\fR, or for multiple arms return \f(CW\*(C`(0, $arms * 2**$level \- 1)\*(C'\fR. .Sp There are 2^level segments comprising the dragon, or arms*2^level when multiple arms, numbered starting from 0. .SH "FORMULAS" .IX Header "FORMULAS" .SS "X,Y to N" .IX Subsection "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 \f(CW\*(C`DragonCurve\*(C'\fR at each level. In midpoint coordinates an adjustment subtracting 0 or 1 must be applied to move an X,Y which is either N=2k or N=2k+1 to the position where dividing out i+1 gives the N=k X,Y. .PP 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. .PP .Vb 9 \& 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 .Ve .PP The same tables work for both the main curve and for the rotated copies per \&\*(L"Arms\*(R" above. .PP .Vb 1 \& until \-1<=X<=0 and 0<=Y<=1 \& \& 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 # bits of N low to high .Ve .PP The X,Y reduction stops at one of the start points for the four arms .PP .Vb 6 \& X,Y endpoint Arm +\-\-\-+\-\-\-+ \& \-\-\-\-\-\-\-\-\-\-\-\- \-\-\- | 2 | 1 | Y=1 \& 0, 0 0 +\-\-\-+\-\-\-+ \& 0, 1 1 | 3 | 0 | Y=0 \& \-1, 1 2 +\-\-\-+\-\-\-+ \& \-1, 0 3 X=\-1 X=0 .Ve .PP 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. .PP For bignum calculations there's no need to apply the \*(L"/2\*(R" 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. .SS "Boundary" .IX Subsection "Boundary" Taking unit squares at each point, the boundary MB[k] of the resulting shape from 0 to N=2^k\-1 inclusive can be had from the boundary B[k] of the plain dragon curve. Taking points N=0 to N=2^k\-1 inclusive is the midpoints of the dragon curve line segments N=0 to N=2^k inclusive. .PP .Vb 2 \& MB[k] = B[k] + 2 \& = 4, 6, 10, 18, 30, 50, 86, 146, 246, 418, 710, 1202, ... \& \& 2 + x + 2*x^2 \& generating function 2 * \-\-\-\-\-\-\-\-\-\-\-\-\- \& 1 \- x \- 2*x^3 .Ve .PP A unit square at the midpoint is a diamond on a dragon line segment .PP .Vb 5 \& / \e \& / \e midpoint m \& *\-\-m\-\-* diamond on dragon curve line segment \& \e / \& \e / .Ve .PP A boundary segment of the dragon curve has two sides of the diamond which are boundary. But when the boundary makes a right hand turn two such sides touch and are therefore not midpoint boundary. .PP .Vb 7 \& /^\e \& / | \e right turn \& \e | //\e two diamond sides touch \& \e|// \e \& *<\-\-\-\-* \& \e / \& \e / .Ve .PP The dragon curve at N=0 points East and the last segment N=2^k\-1 to N=2^k is North. Since the curve never overlaps itself this means that when going around the right side of the curve there is 1 more left turn than right turn, .PP .Vb 1 \& lefts \- rights = 1 .Ve .PP The total line segments on the right is the dragon curve R[k] and there are R[k]\-1 turns, so the total turns lefts+rights is .PP .Vb 1 \& lefts + rights + 1 = R[k] .Ve .PP So the lefts and rights are obtained separately .PP .Vb 2 \& 2*lefts = R[k] adding the two equations \& 2*rights = R[k] \- 2 subtracting the two equations .Ve .PP The result is then .PP .Vb 3 \& MR[k] = 2*R[k] \- 2*rights \& = 2*R[k] \- 2*(R[k]\-2)/2 \& = R[k] + 2 .Ve .PP A similar calculation is made on the left side of the curve. The net turn is the same and so the same lefts\-rights=1 and thus from the dragon curve L[k] left boundary .PP .Vb 3 \& ML[k] = 2*L[k] \- 2*lefts \& = 2*L[k] \- 2*(L[k]/2) \& = L[k] .Ve .PP The total is then .PP .Vb 3 \& MB[k] = MR[k] + ML[k] \& = R[k]+2 + L[k] \& = B[k] + 2 since B[k]=R[k]+L[k] .Ve .PP The generating function can be had from the partial fractions form of the dragon curve boundary. B[k]+2 means adding 2/(1\-x) which cancels out the \&\-2/(1\-x) in gB(x). .SH "OEIS" .IX Header "OEIS" The \f(CW\*(C`DragonMidpoint\*(C'\fR is in Sloane's Online Encyclopedia of Integer Sequences as .Sp .RS 4 (etc) .RE .PP .Vb 4 \& 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) \& A203175 boundary of unit squares N=0 to N=2^k\-1, value 4 onwards .Ve .SS "A073089" .IX Subsection "A073089" For A073089=abs(dY), the midpoint curve is vertical when the \f(CW\*(C`DragonCurve\*(C'\fR has a vertical followed by a left turn, or horizontal followed by a right turn. \f(CW\*(C`DragonCurve\*(C'\fR verticals are whenever N is odd, and the turn is the bit above the lowest 0 in N (per \*(L"Turn\*(R" in Math::PlanePath::DragonCurve). So .PP .Vb 1 \& abs(dY) = lowbit(N) XOR bit\-above\-lowest\-zero(N) .Ve .PP The n in 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). .PP The mod\-16 definitions in A073089 express combinations of N odd/even and bit\-above\-low\-0 which are the vertical midpoint segments. The recurrence a(8n+1)=a(4n+1) acts to strip zeros above a low 1 bit, .PP .Vb 2 \& n = 0b..uu0001 \& \-> 0b...uu001 .Ve .PP In terms of N=n\-2 this reduces .PP .Vb 2 \& N = 0b..vv1111 \& \-> 0b...vv111 .Ve .PP which has the effect of seeking a lowest 0 in the range of the mod\-16 conditions. .SH "SEE ALSO" .IX Header "SEE ALSO" Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::DragonRounded .PP Math::PlanePath::AlternatePaperMidpoint, Math::PlanePath::R5DragonMidpoint, Math::PlanePath::TerdragonMidpoint .SH "HOME PAGE" .IX Header "HOME PAGE" .SH "LICENSE" .IX Header "LICENSE" Copyright 2011, 2012, 2013, 2014 Kevin Ryde .PP Math-PlanePath is free software; you can redistribute it and/or modify it under the terms of the \s-1GNU\s0 General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. .PP Math-PlanePath is distributed in the hope that it will be useful, but \&\s-1WITHOUT ANY WARRANTY\s0; without even the implied warranty of \s-1MERCHANTABILITY\s0 or \s-1FITNESS FOR A PARTICULAR PURPOSE. \s0 See the \s-1GNU\s0 General Public License for more details. .PP You should have received a copy of the \s-1GNU\s0 General Public License along with Math-PlanePath. If not, see .