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 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 and X=Y diagonal points once each, and visits "inside" points between there twice. 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 are the integers which have only digits 0 and 1 in base 4, or equivalently those which have a 0 bit at each even numbered bit position.
The X=Y diagonal N=0,2,8,10,32,etc are the integers which have only digits 0 and 2 in base 4, or equivalently which have a 0 bit at each odd 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 quite different.
The curve arises from thinking of a strip of paper folded in half alternately one way and the other, then unfolded so each crease is a 90 degree angle. The effect is that the curve repeats in successive doublings turned by 90 degrees and reversed.
The first segment N=0 to N=1 unfolds, pivoting at the end "1",
2 -> | unfold / | ===> | | | 0------1 0-------1
Then 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 4
In general after each unfold the shape is a triangle,
. . /| / \ / | / \ / | / \ / | / \ / | / \ /_____| /___________\ 0,0 0,0 after even number after odd number of unfolds, of unfolds, N=0 to N=2^even N=0 to N=2^odd
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 \| +----+----+
At each point N the curve always turns either to the 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 (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, the lowest 1 bit is the 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 (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=0b1010 the lowest 0 is the least significant bit, and above that is a 1 at odd pos=1, so turn right.
The inversion for odd bit positions can be applied with an xor 0xAA..AA, after which the calculations are the sames as the DragonCurve (see "Turns" in Math::PlanePath::DragonCurve).
See "FUNCTIONS" in Math::PlanePath for the 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 can 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.
The alternate paper folding curve is in Sloane's Online Encyclopedia of Integer Sequences as,
http://oeis.org/A106665 A106665 -- turn, 1=left,0=right, starting at N=1
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::ZOrderCurve
http://user42.tuxfamily.org/math-planepath/index.html
Copyright 2010, 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.