Provided by: libmath-planepath-perl_113-1_all 
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
| | | | | |
^
-2 -1 -2 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". There may be none, one or
two N's for a given "$x,$y", and for arms>=2 there are three N's at the starting X,Y
points.
"$n = $path->n_start()"
Return 0, the first N in the path.
FORMULAS
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. If that's
done then the turn calculation is 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 the Y, 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. The
changes are the Golay-Rudin-Shapiro sequence, which is a parity 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 has two 11 bit pairs.
The GRS is -1 on an even length run, for example 1111 has 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 edge outer X,Y points once each and inner X,Y points twice each
means an anti-diagonal d=X+Y is visited a total of d many times. The diagonal has
floor(d/2)+1 many points. When d is odd the first is visited once and the rest visited
twice. When d is even the X=Y point is only visited once. In each case the total is d
many visits.
The way the coordinate sum d=X+Y occurs d 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)
A106665 next turn 1=left,0=right, a(0) is turn at N=1
A209615 turn 1=left,-1=right
A020985 Golay/Rudin/Shapiro sequence +1,-1
dX and dY alternately
dSum, change in X+Y
A020986 Golay/Rudin/Shapiro cumulative
X coordinate (undoubled)
X+Y coordinate sum
A020990 Golay/Rudin/Shapiro * (-1)^n cumulative
Y coordinate (undoubled)
X-Y diff, starting from N=1
A020987 GRS with values 0,1 instead of +1,-1
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.
A077957 Y at N=2^k, being alternately 0 and 2^(k/2)
A000695 N on X axis, base 4 digits 0,1 only
A062880 N on diagonal, base 4 digits 0,2 only
A022155 N positions of left or down segment,
being GRS < 0,
ie. dSum < 0 so move to previous anti-diagonal
A203463 N positions of up or right segment,
being GRS > 0,
ie. dSum > 0 so move to next anti-diagonal
A020991 N-1 of first time on X+Y=k anti-diagonal
A212591 N-1 of last time on X+Y=k anti-diagonal
A093573 N-1 of points on the anti-diagonals d=X+Y,
by ascending N-1 value within each diagonal
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.
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 Mendes 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 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/>.