Provided by: libmath-planepath-perl_125-1_all bug

NAME

       Math::PlanePath::AlternatePaper -- alternate paper folding curve

SYNOPSIS

        use Math::PlanePath::AlternatePaper;
        my $path = Math::PlanePath::AlternatePaper->new;
        my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

       This is an integer version of the alternate paper folding curve (a variation on the DragonCurve paper
       folding).

             8 |                                                      128
               |                                                       |
             7 |                                                42---43/127
               |                                                |      |
             6 |                                         40---41/45--44/124
               |                                         |      |      |
             5 |                                  34---35/39--38/46--47/123
               |                                  |      |      |      |
             4 |                           32---33/53--36/52--37/49--48/112
               |                           |      |      |      |      |
             3 |                    10---11/31--30/54--51/55--50/58--59/111
               |                    |      |      |      |      |      |
             2 |              8----9/13--12/28--29/25--24/56--57/61--60/108
               |              |     |      |      |      |      |      |
             1 |        2----3/7---6/14--15/27--26/18--19/23---22/62--63/107
               |        |     |     |      |      |      |      |      |
           Y=0 |  0-----1     4-----5     16-----17     20-----21     64---..
               |
               +------------------------------------------------------------
                 X=0    1     2     3      4      5      6      7      8

       The curve visits the X axis points and the X=Y diagonal points once each and visits "inside" points
       between there twice each.  The first doubled point is X=2,Y=1 which is N=3 and also N=7.  The segments
       N=2,3,4 and N=6,7,8 have touched, but the curve doesn't cross over itself.  The doubled vertices are all
       like this, touching but not crossing, and no edges repeat.

       The first step N=1 is to the right along the X axis and the path fills the eighth of the plane up to the
       X=Y diagonal inclusive.

       The X axis N=0,1,4,5,16,17,etc is the integers which have only digits 0,1 in base 4, or equivalently
       those which have a 0 bit at each odd numbered bit position.

       The X=Y diagonal N=0,2,8,10,32,etc is the integers which have only digits 0,2 in base 4, or equivalently
       those which have a 0 bit at each even numbered bit position.

       The X axis values are the same as on the ZOrderCurve X axis, and the X=Y diagonal is the same as the
       ZOrderCurve Y axis, but in between the two are different.  (See Math::PlanePath::ZOrderCurve.)

   Paper Folding
       The curve arises from thinking of a strip of paper folded in half alternately one way and the other, and
       then unfolded so each crease is a 90 degree angle.  The effect is that the curve repeats in successive
       doublings turned 90 degrees and reversed.

       The first segment N=0 to N=1 unfolds clockwise, pivoting at the endpoint "1",

                                           2
                                      ->   |
                        unfold       /     |
                         ===>       |      |
                                           |
           0------1                0-------1

       Then that "L" shape unfolds again, pivoting at the end "2", but anti-clockwise, on the opposite side to
       the first unfold,

                                           2-------3
                  2                        |       |
                  |     unfold             |   ^   |
                  |      ===>              | _/    |
                  |                        |       |
           0------1                0-------1       4

       In general after each unfold the shape is a triangle as follows.  "N" marks the N=2^k endpoint in the
       shape, either bottom right or top centre.

           after even number          after odd number
              of unfolds,                of unfolds,
            N=0 to N=2^even            N=0 to N=2^odd

                      .                       N
                     /|                      / \
                    / |                     /   \
                   /  |                    /     \
                  /   |                   /       \
                 /    |                  /         \
                /_____N                 /___________\
               0,0                     0,0

       For an even number of unfolds the triangle consists of 4 sub-parts numbered by the high digit of N in
       base 4.  Those sub-parts are self-similar in the direction ">", "^" etc as follows, and with a reversal
       for parts 1 and 3.

                     +
                    /|
                   / |
                  /  |
                 / 2>|
                +----+
               /|\  3|
              / | \ v|
             /  |^ \ |
            / 0>| 1 \|
           +----+----+

   Arms
       The "arms" parameter can choose 1 to 8 curve arms successively advancing.  Each fills an eighth of the
       plane.  The second arm is mirrored across the X=Y leading diagonal, so

             arms => 2

               |   |     |       |       |       |
             4 |  33---31/55---25/57---23/63---64/65--
               |         |       |       |       |
             3 |  11---13/29---19/27---20/21---22/62--
               |   |     |       |       |       |
             2 |   9----7/15---16/17---18/26---24/56--
               |         |       |       |       |
             1 |   3----4/5-----6/14---12/28---30/54--
               |   |     |       |       |       |
           Y=0 |  0/1----2       8------10      32---
               |
               +------------- -------------------------
                 X=0     1       2       3       4

       Here the even N=0,2,4,6,etc is the plain curve below the X=Y diagonals and odd N=1,3,5,7,9,etc is the
       mirrored copy.

       Arms 3 and 4 are the same but rotated +90 degrees and starting from X=0,Y=1.  That start point ensures
       each edge between integer points is traversed just once.

           arms => 4

               |       |       |      |        |
           --34/35---14/30---18/21--25/57----37/53--        3
               |       |       |      |        |
           --15/31---10/11----6/17--13/29----32/33--        2
               |       |       |      |        |
            --19       7-----2/3/5---8/9-----12/28--        1
                               |      |        |
                              0/1-----4        16--     <- Y=0

           -----------------------------------------
              -1      -2      X=0     1        2

       Points N=0,4,8,12,etc is the plain curve, N=1,5,9,13,etc the second mirrored arm, N=2,6,10,14,etc is arm
       3 which is the plain curve rotated +90, and N=3,7,11,15,etc the rotated and mirrored.

       Arms 5 and 6 start at X=-1,Y=1, and arms 7 and 8 start at X=-1,Y=0 so they too traverse each edge once.
       With a full 8 arms each point is visited twice except for the four start points which are three times.

           arms => 8

               |       |       |       |       |       |
           --75/107--66/67---26/58---34/41---49/113--73/105--        3
               |       |       |       |       |       |
           --51/115---27/59---18/19--10/33---25/57---64/65--         2
               |       |       |       |       |       |
           --36/43---12/35---4/5/11---2/3/9--16/17---24/56--         1
               |       |       |       |       |       |
           --28/60---20/21---6/7/13--0/1/15---8/39---32/47--     <- Y=0
               |       |       |       |       |       |
           --68/69---29/61----14/37---22/23--31/63---55/119--       -1
               |       |       |       |       |       |
           --77/109--53/117---38/45---30/62--70/71---79/111--       -2
               |       |       |       |       |       |

                                       ^
              -3      -2      -1      X=0     1        2

FUNCTIONS

       See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.

       "$path = Math::PlanePath::AlternatePaper->new ()"
       "$path = Math::PlanePath::AlternatePaper->new (arms => $integer)"
           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 points.

       "@n_list = $path->xy_to_n_list ($x,$y)"
           Return a list of N point numbers for coordinates "$x,$y".

           For arms=1 there may be none, one or two N's for a given "$x,$y".  For multiple arms the origin
           points X=0 or 1 and Y=0 or -1 have up to 3 Ns, being the starting points of the arms.  For arms=8
           those 4 points have 3 N and every other "$x,$y" has exactly two Ns.

       "$n = $path->n_start()"
           Return 0, the first N in the path.

   Level Methods
       "($n_lo, $n_hi) = $path->level_to_n_range($level)"
           Return "(0, 2**$level)", or for multiple arms return "(0, $arms * 2**$level + ($arms-1))".

           This is the same as "Level Methods" in Math::PlanePath::DragonCurve.  Each level is an unfold (on
           alternate sides left or right).

FORMULAS

       Various formulas for coordinates, lengths and area can be found in the author's mathematical write-up

           <http://user42.tuxfamily.org/alternate/index.html>

   Turn
       At each point N the curve always turns either left or right, it never goes straight ahead.  The turn is
       given by the bit above the lowest 1 bit in N and whether that position is odd or even.

           N = 0b...z100..00   (including possibly no trailing 0s)
                    ^
                    pos, counting from 0 for least significant bit

           (z bit) XOR (pos&1)   Turn
           -------------------   ----
                    0            right
                    1            left

       For example N=10 binary 0b1010 has lowest 1 bit at 0b__1_ and the bit above that is a 0 at even number
       pos=2, so turn to the right.

   Next Turn
       The bits also give the turn after next by looking at the bit above the lowest 0.

           N = 0b...w011..11    (including possibly no trailing 1s)
                    ^
                    pos, counting from 0 for least significant bit

           (w bit) XOR (pos&1)    Next Turn
           -------------------    ---------
                    0             right
                    1             left

       For example at N=10 binary 0b1010 the lowest 0 is the least significant bit, and above that is a 1 at odd
       pos=1, so at N=10+1=11 turn right.  This works simply because w011..11 when incremented becomes w100..00
       which is the "z" form above.

       The inversion at odd bit positions can be applied with an xor 0b1010..1010.  With that done the turn
       calculation is then the same as the DragonCurve (see "Turn" in Math::PlanePath::DragonCurve).

   Total Turn
       The total turn can be calculated from the segment replacements resulting from the bits of N.

           each bit of N from high to low

             when plain state
              0 -> no change
              1 -> turn left if even bit pos or turn right if odd bit pos
                     and go to reversed state

             when reversed state
              1 -> no change
              0 -> turn left if even bit pos or turn right if odd bit pos
                     and go to plain state

           (bit positions numbered from 0 for the least significant bit)

       This is similar to the DragonCurve (see "Total Turn" in Math::PlanePath::DragonCurve) except the turn is
       either left or right according to an odd or even bit position of the transition, instead of always left
       for the DragonCurve.

   dX,dY
       Since there's always a turn either left or right, never straight ahead, the X coordinate changes, then Y
       coordinate changes, alternately.

               N=0
           dX   1  0  1  0  1  0 -1  0  1  0  1  0 -1  0  1  0  ...
           dY   0  1  0 -1  0  1  0  1  0  1  0 -1  0 -1  0 -1  ...

       X changes when N is even, Y changes when N is odd.  Each change is either +1 or -1.  Which it is follows
       the Golay-Rudin-Shapiro sequence which is parity odd or even of the count of adjacent 11 bit pairs.

       In the total turn above it can be seen that if the 0->1 transition is at an odd position and 1->0
       transition at an even position then there's a turn to the left followed by a turn to the right for no net
       change.  Likewise an even and an odd.  This means runs of 1 bits with an odd length have no effect on the
       direction.  Runs of even length on the other hand are a left followed by a left, or a right followed by a
       right, for 180 degrees, which negates the dX change.  Thus

           if N even then dX = (-1)^(count even length runs of 1 bits in N)
           if N odd  then dX = 0

       This (-1)^count is related to the Golay-Rudin-Shapiro sequence,

           GRS = (-1) ^ (count of adjacent 11 bit pairs in N)
               = (-1) ^ count_1_bits(N & (N>>1))
               = /  +1 if (N & (N>>1)) even parity
                 \  -1 if (N & (N>>1)) odd parity

       The GRS is +1 on an odd length run of 1 bits, for example a run 111 is two 11 bit pairs.  The GRS is -1
       on an even length run, for example 1111 is three 11 bit pairs.  So modulo 2 the power in the GRS is the
       same as the count of even length runs and therefore

           dX = /  GRS(N)  if N even
                \  0       if N odd

       For dY the total turn and odd/even runs of 1s is the same 180 degree changes, except N is odd for a Y
       change so the least significant bit is 1 and there's no return to "plain" state.  If this lowest run of
       1s starts on an even position (an odd number of 1s) then it's a turn left for +1.  Conversely if the run
       started at an odd position (an even number of 1s) then a turn right for -1.  The result for this last run
       is the same "negate if even length" as the rest of the GRS, just for a slightly different reason.

           dY = /  0       if N even
                \  GRS(N)  if N odd

   dX,dY Pair
       At a consecutive pair of points N=2k and N=2k+1 the dX and dY can be expressed together in terms of
       GRS(k) as

           dX = GRS(2k)
              = GRS(k)

           dY = GRS(2k+1)
              = GRS(k) * (-1)^k
              = /  GRS(k) if k even
                \  -GRS(k) if k odd

       For dY reducing 2k+1 to k drops a 1 bit from the low end.  If the second lowest bit is also a 1 then they
       were a "11" bit pair which is lost from GRS(k).  The factor (-1)^k adjusts for that, being +1 if k even
       or -1 if k odd.

   dSum
       From the dX and dY formulas above it can be seen that their sum is simply GRS(N),

           dSum = dX + dY = GRS(N)

       The sum X+Y is a numbering of anti-diagonal lines,

          | \ \ \
          |\ \ \ \
          | \ \ \ \
          |\ \ \ \ \
          | \ \ \ \ \
          |\ \ \ \ \ \
          +------------
            0 1 2 3 4 5

       The curve steps each time either up to the next or back to the previous according to dSum=GRS(N).

       The way the curve visits outside edge X,Y points once each and inner X,Y points twice each means an anti-
       diagonal s=X+Y is visited a total of s many times.  The diagonal has floor(s/2)+1 many points.  When s is
       odd the first is visited once and the rest visited twice.  When s is even the X=Y point is only visited
       once.  In each case the total is s many visits.

       The way the coordinate sum s=X+Y occurs s many times is a geometric interpretation to the way the
       cumulative GRS sequence has each value k occurring k many times.  (See
       Math::NumSeq::GolayRudinShapiroCumulative.)

OEIS

       The alternate paper folding curve is in Sloane's Online Encyclopedia of Integer Sequences as

           <http://oeis.org/A106665> (etc)

           A020986   X coordinate unduplicated, X+Y coordinate sum
                       being Golay/Rudin/Shapiro cumulative
           A020990   Y coordinate unduplicated, X-Y diff starting from N=1
                       being Golay/Rudin/Shapiro * (-1)^n cumulative
           A068915   Y when N even, X when N odd

       Since the X and Y coordinates each change alternately, each coordinate appears twice, for instance
       X=0,1,1,2,2,3,3,2,2,etc.  A020986 and A020990 are "undoubled" X and Y in the sense of just one copy of
       each of those paired values.

           A209615   turn 1=left,-1=right
           A292077   turn 0=left,1=right
           A106665   next turn 1=left,0=right, a(0) is turn at N=1
           A020985   dX and dY alternately, dSum change in X+Y
                       being Golay/Rudin/Shapiro sequence +1,-1
           A020987   GRS with values 0,1 instead of +1,-1

           A077957   Y at N=2^k, being alternately 0 and 2^(k/2)

           A000695   N on X axis, being base 4 digits 0,1 only
           A007088     in base-4
           A151666   predicate 0,1 for N on X axis
           A062880   N on diagonal, being base 4 digits 0,2 only
           A169965     in base-4

           A126684   N single-visited points, either X axis or diagonal
           A176237   N double-visited points

           A270804   N segments of X=Y diagonal stair-step
           A270803     0,1 predicate for these segments

           A022155   N positions of West or South segments,
                       being GRS < 0,
                       ie. dSum < 0 so move to previous anti-diagonal
           A203463   N positions of East or North segments,
                       being GRS > 0,
                       ie. dSum > 0 so move to next anti-diagonal

           A212591   N-1 of first time on X+Y=s anti-diagonal
           A047849   N of first time on X+Y=2^k anti-diagonal

           A020991   N-1 of last time on X+Y=s anti-diagonal
           A053644   X of last time on X+Y=s anti-diagonal
           A053645   Y of last time on X+Y=s anti-diagonal
           A080079   X-Y of last time on X+Y=s anti-diagonal

           A093573   N-1 of points on the anti-diagonals d=X+Y,
                       by ascending N-1 value within each diagonal
           A004277   num visits in column X

       A020991 etc have values N-1, ie. the numbering differs by 1 from the N here, since they're based on the
       A020986 cumulative GRS starting at n=0 for value GRS(0).  This matches the turn sequence A106665 starting
       at n=0 for the first turn, whereas for the path here that's N=1.

           A274230   area to N=2^k = double-visited points to N=2^k
           A027556   2*area to N=2^k
           A134057   area to N=4^k
           A060867   area to N=2*4^k
           A122746   area increment N=2^k to N=2^(k+1)
                       = num segments West  N=0 to 2^k-1

           A005418   num segments East  N=0 to 2^k-1
           A051437   num segments North N=0 to 2^k-1
           A007179   num segments South N=0 to 2^k-1
           A097038   num runs of 8 consecutive segments within N=0 to 2^k-1
                       each segment enclosing a new unit square

           A000225   convex hull area*2, being 2^k-1

           A027383   boundary/2 to N=2^k
                      also boundary verticals or horizontals
                      (boundary is half verticals half horizontals)
           A131128   boundary to N=4^k
           A028399   boundary to N=2*4^k

           A052955   single-visited points to N=2^k
           A052940   single-visited points to N=4^k, being 3*2^n-1

           A181666   n XOR other(n) occurring at double-visited points
           A086341   graph diameter of level N=0 to 2^k  (for k>=3)

           arms=2
             A062880   N on X axis, base 4 digits 0,2 only

           arms=3
             A001196   N on X axis, base 4 digits 0,3 only

SEE ALSO

       Math::PlanePath, Math::PlanePath::AlternatePaperMidpoint

       Math::PlanePath::DragonCurve, Math::PlanePath::CCurve, Math::PlanePath::HIndexing,
       Math::PlanePath::ZOrderCurve

       Math::NumSeq::GolayRudinShapiro, Math::NumSeq::GolayRudinShapiroCumulative

       Michel Mendès France and G. Tenenbaum, "Dimension des Courbes Planes, Papiers Plies et Suites de Rudin-
       Shapiro", Bulletin de la S.M.F., volume 109, 1981, pages 207-215.
       <http://www.numdam.org/item?id=BSMF_1981__109__207_0>

HOME PAGE

       <http://user42.tuxfamily.org/math-planepath/index.html>

LICENSE

       Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017 Kevin Ryde

       This file is part of Math-PlanePath.

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