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 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 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.
Paper Folding
The curve arises from thinking of a strip of paper folded in half alternately one way and the other, and which is 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, pivoting at the end "1",
2
-> |
unfold / |
===> | |
|
0------1 0-------1Then that "L" shape unfolds again, pivoting at the end "2", but 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,
after even number after odd number
of unfolds, of unfolds,
N=0 to N=2^even N=0 to N=2^odd
. .
/| / \
/ | / \
/ | / \
/ | / \
/ | / \
/_____| /___________\
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 can 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 for odd bit positions can be applied with an xor 0xAA..AA, and after 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, 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 evenThis 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. On an even length run the GRS is -1. 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 so
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. This lowest run of 1s will be turn left giving dY=+1 if it started at an even position (an odd number of 1s), and conversely turn right for dY=-1 if at an odd position (an even number of 1s). The result for this last run is the same negate if even length, just for a slightly different reason.
dY = 0 if N even
GRS(N) if N oddAdjacent dX then dY at N=2k and N=2k+1 can be expressed together in terms of that k as
dX = GRS(2k)
= GRS(k)
dY = GRS(2k+1)
= GRS(k) * (-1)^k
= GRS(k) if k even or -GRS(k) if k oddGoing from 2k+1 to k drops a 1 bit from the low end and 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 accounts for that, being +1 if k even or -1 if k odd.
From the dX and dY formulas 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 The curve steps each time either up to the next or back to the previous according as dSum=GRS(N), though this doesn't say where along the diagonal each N is.
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
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.
SEE ALSO
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::CCurve, Math::PlanePath::HIndexing, Math::PlanePath::ZOrderCurve
HOME 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/>.