The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.
 / 
Math-PlanePath-68
River stage one • 3 direct dependents • 4 total dependents
2 ++
/ Math::PlanePath::DragonMidpoint

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 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.

Arms

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 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   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.

FUNCTIONS

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.

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 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.

OEIS

The DragonMidpoint is in Sloane's Online Encyclopedia of Integer Sequences as

    http://oeis.org/A073089

    A073089 -- 0=horizontal, 1=vertical (extra initial 0)

The midpoint curve is vertical when the DragonCurve has a vertical followed by left turn or horizontal followed by right turn. The DragonCurve verticals are whenever N is odd, and the following turn is either the bit above the lowest 0 in N as per "Turns" in Math::PlanePath::DragonCurve.

The mod-16 definitions in A073089 express the combinations of N odd/even and bit-above-low-0 which make a vertical. But note the n of A073089 is n=N+2 in the numbering of this DragonMidpoint, and the initial value at n=1 has no corresponding point in DragonMidpoint (it would be N=-1).

The recursion a(8n+1)=a(4n+1) in A073089 works to reduce an N=0b..0111 to 0b..011 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 unless there's no more than two of them. In terms of n it's a strip of zeros above a low 1 bit n=0b...00001 -> 0b...01.

SEE ALSO

Math::PlanePath, Math::PlanePath::DragonCurve, 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/>.