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 8The curve visits the X axis points and 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 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-------1Then 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 4In general after each unfold the shape is a triangle as follows. The "N" marks the N=2^k endpoint in the shape, 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,0For 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 shown, and with a reversal for parts 1 and 3.
+
/|
/ |
/ |
/ 2>|
+----+
/|\ 3|
/ | \ v|
/ |^ \ |
/ 0>| 1 \|
+----+----+FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::AlternatePaper->new ()-
Create and return a new path object.
($x,$y) = $path->n_to_xy ($n)-
Return the X,Y coordinates of point number
$non the path. Points begin at 0 and if$n < 0then 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. $n = $path->n_start()-
Return 0, the first N in the path.
FORMULAS
Turns
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 leftFor 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.
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 leftFor 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.
The inversion at odd bit positions can be applied with an xor 0b1010..1010, after which that the calculations are the same as the DragonCurve (see "Turns" 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 ("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, then the X again, etc, alternately, and each time by either +1 or -1. The changes are the Golay-Rudin-Shapiro sequence, which is the parity 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
dX = / (-1) ^ (count of even length runs of 1 bits in N),
| if N even,
\ or 0 if N oddThis (-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 parityThe 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 oddFor dY the total turn and odd/even runs of 1s makes the same 180 degree changes, except N is odd for 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 oddConsecutive dX,dY
At consecutive points N=2k and N=2k+1 the dX an 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 oddReducing 2k+1 to k drops a 1 bit from the low end. If the second lowest bit is also a 1 then they're a 11 bit pair which is lost in 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 5The curve steps each time either up to the next or back to the previous according to dSum=GRS(N).
The way the curve visits the outside points once each and the inside points twice each means the visits an anti-diagonal d=X+Y a total of d many times. Such a diagonal has floor(d/2)+1 many points, the first visited once, the rest visited twice, except when d is even the X=Y point is only visited once. In each case the total is total d many visits.
This sum d=X+Y occurring d many times gives 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 turn, 1=left,0=right, starting at N=1
A020985 Golay/Rudin/Shapiro sequence
dX and dY, skipping every second value zero
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=1Since the X and Y coordinates change each 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.
A000695 N on X axis, base 4 digits 0,1 only
A062880 N on diagonal, base 4 digits 0,2 only
A022155 positions where GRS < 0, which is
N where down or left step, ie. dSum < 0,
moving to the previous anti-diagonal
A203463 positions where GRS > 0, which is
N where up or right step, ie. dSum > 0,
moving to the 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,
in ascending N-1 within each diagonalSEE ALSO
Math::PlanePath, 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_0HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
Copyright 2011, 2012 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/>.