view release on metacpan or  search on metacpan

lib/Math/PlanePath/AlternatePaper.pm  view on Meta::CPAN

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

=head1 FUNCTIONS

See L<Math::PlanePath/FUNCTIONS> for behaviour common to all path classes.

=over 4

=item C<$path = Math::PlanePath::AlternatePaper-E<gt>new ()>

=item C<$path = Math::PlanePath::AlternatePaper-E<gt>new (arms =E<gt> $integer)>

Create and return a new path object.

=item C<($x,$y) = $path-E<gt>n_to_xy ($n)>

Return the X,Y coordinates of point number C<$n> on the path.  Points begin
at 0 and if C<$n E<lt> 0> then the return is an empty list.

Fractional positions give an X,Y position along a straight line between the
integer points.

=item C<@n_list = $path-E<gt>xy_to_n_list ($x,$y)>

Return a list of N point numbers for coordinates C<$x,$y>.

For arms=1 there may be none, one or two N's for a given C<$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 C<$x,$y> has exactly two Ns.

=item C<$n = $path-E<gt>n_start()>

Return 0, the first N in the path.

=back

=head2 Level Methods

=over

=item C<($n_lo, $n_hi) = $path-E<gt>level_to_n_range($level)>

Return C<(0, 2**$level)>, or for multiple arms return C<(0, $arms *
2**$level + ($arms-1))>.

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

=back

=head1 FORMULAS

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

=over

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

=back

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

=head2 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
L<Math::PlanePath::DragonCurve/Turn>).

=head2 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

lib/Math/PlanePath/AlternatePaper.pm  view on Meta::CPAN

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-E<gt>1 transition is at
an odd position and 1-E<gt>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

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

=head2 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 L<Math::NumSeq::GolayRudinShapiroCumulative>.)

=head1 OEIS

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

=over

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

=back

    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