Math::PlanePath::AlternatePaper -- alternate paper folding curve
use Math::PlanePath::AlternatePaper; my $path = Math::PlanePath::AlternatePaper->new; my ($x, $y) = $path->n_to_xy (123);
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 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.)
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. 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,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 shown, and with a reversal for parts 1 and 3.
+ /| / | / | / 2>| +----+ /|\ 3| / | \ v| / |^ \ | / 0>| 1 \| +----+----+
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 $n on the path. Points begin at 0 and if $n < 0 then the return is an empty list.
$n
$n < 0
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.
$x,$y
$n = $path->n_start()
Return 0, the first N in the path.
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.
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.
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).
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.
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 odd
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 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 odd
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 odd
Reducing 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.
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 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.)
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=1
Since 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 diagonal
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_0
http://user42.tuxfamily.org/math-planepath/index.html
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/>.
To install Math::PlanePath, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Math::PlanePath
CPAN shell
perl -MCPAN -e shell install Math::PlanePath
For more information on module installation, please visit the detailed CPAN module installation guide.