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 points and the 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 sections 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 N=0,1,4,5,16,17,etc on the X axis are the integers which have only digits 0 and 1 in base 4, or equivalently which have a 0 bit at each even position.
The N=0,2,8,10,32,etc on the X=Y diagonals are are the integers which have only digits 0 and 2 in base 4, or equivalently which have a 0 bit at each odd position.
Those X axis values are the same as on the ZOrderCurve X axis, and the diagonal is the same as the ZOrderCurve Y axis, though in between the two are quite different.
Paper Folding
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 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,
. .
/| / \
/ | / \
/ | / \
/ | / \
/ | / \
/_____| /___________\
0,0 0,0
after even number after odd number
of unfolds, being of unfolds, being
N=0 to N=2^even N=0 to N=2^oddFor an even number of unfolds the triangle consists of 4 sub-parts which are the high digit of N in base 4, and those sub-parts are self-similar in the ">" etc direction shown, and reversed for parts 1 and 3.
+
/|
/ |
/ |
/ 2>|
+----+
/|\ 3|
/ | \ v|
/ |^ \ |
/ 0>| 1 \|
+----+----+Turns
At each point N the curve always turns either to the left or right, it never goes straight ahead. The bit above the lowest 1 bit in N and whether that position is odd or even gives the turn direction.
N = 0b...z100..00 (possibly no trailing 0s)
^
pos, counting from 0 for least significant bit
(z bit) ^ (pos&1) Turn
----------------- ----
0 right
1 leftFor example N=10 binary 0b1010, the lowest 1 bit is the 0b..1. and the bit above that is a 0 at even 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) ^ (pos&1) Next Turn
----------------- ---------
0 right
1 leftFor 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 at odd 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).
FUNCTIONS
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
$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 positions.
$n = $path->n_start()-
Return 0, the first N in the path.
OEIS
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=1SEE ALSO
Math::PlanePath, Math::PlanePath::DragonCurve, Math::PlanePath::ZOrderCurve
HOME PAGE
http://user42.tuxfamily.org/math-planepath/index.html
LICENSE
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/>.