NAME
Math::PlanePath::AR2W2Curve  2x2 selfsimilar curve of four patterns
SYNOPSIS
use Math::PlanePath::AR2W2Curve;
my $path = Math::PlanePath::AR2W2Curve>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an integer version of the AR2W2 curve per
Asano, Ranjan, Roos, Welzl and Widmayer "SpaceFilling Curves and Their Use in the Design of Geometric Data Structures", Theoretical Computer Science, volume 181, issue 1, pages 315, July 1997.
And in LATIN'95 Theoretical Informatics which is at Google Books http://books.google.com.au/books?id=_aKhJUJunYwC&pg=PA36
It traverses the first quadrant in selfsimilar 2x2 blocks which are a mixture of "U" and "Z" shapes. The mixture is designed to improve some locality measures (how big the N range for a given region).

7 424344 474849 6263
\    
6 4041 4546 5150 6160
  
5 39 363534 52 5556 59
  /    
4 3837 3332 5354 5758
\
3 6 7 8 10 31 282726
 /    
2 5 4 9 11 3029 2425
  
1 2 3 1312 1718 2322
\    
Y=0 > 0 1 141516 192021
X=0 1 2 3 4 5 6 7
Shape Parts
There's four base patterns A to D. A2 is a mirror image of A1, B2 a mirror of B1, etc. The start is A1, and above that D2, then A1 again, alternately.
^> ^
23 C1  B2 1 3 C2 D1 
A1 \  A2  \  > 
01 ^ 0 2 ^ >
D2  B1 B1 B2
> 
12 C2 B1 12 B2 C1
B1   >> B2   >>
0 3 ^  0 3 ^ 
D1 B2 B1 D2
 v  v
^ \ ^ 
12 B1 \A1 12 A2/  B2
C1    v C2   / v
0 3 ^  0 3 ^ \
/A2 B2 B1 \A1
/ v  v
^  ^ \
12 A2/  C2 12 C1 \A1
D1   / v D2    v
0 3 ^ \ 0 3 ^ 
D1 \A2 /A1 D2
 v / v
For parts which fill on the right such as the B1 and B2 subparts of A1, the numbering must be reversed. This doesn't affect the shape of the curve as such, but it matters for enumerating it as done here.
Start Shape
The default starting shape is the A1 "Z" part, and above it D2. Notice the starting subpart of D2 is A1 and in turn the starting subpart of A1 is D2, so those two alternate at successive higher levels. Their subparts reach all other parts (in all directions, and forward or reverse).
The start_shape => $str
option can select a different starting shape. The choices are
"A1" \ pair
"D2" /
"B2" \ pair
"B1rev" /
"D1rev" \ pair
"A2rev" /
B2 begins with a reversed B1 and in turn a B1 reverse begins with B2 (no reverse), so those two alternate. Similarly D1 reverse starts with A2 reverse, and A2 reverse starts with D1 reverse.
The curve is conceived by the authors as descending into eversmaller subparts and for that any of the patterns can be a toplevel start. But to expand outwards as done here the starting part must be the start of the pattern above it, and that's so only for the 6 listed. The descent graph is
D2rev > D2 <> A1
B2rev >
C2rev > A1rev > B2 <> B1rev < C2
C1rev > < A2 < C1
B1 > D1rev <> A2rev
D1 >
So for example B1 is not at the start of anything. Or A1rev is at the start of C2rev, but then nothing starts with C2rev. Of the 16 total only the three pairs shown "<>" are cycles and can thus extend upwards indefinitely.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::AR2W2Curve>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_lo, $n_hi) = $path>rect_to_n_range ($x1,$y1, $x2,$y2)

The returned range is exact, meaning
$n_lo
and$n_hi
are the smallest and largest in the rectangle.
Level Methods
SEE ALSO
Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::PeanoCurve
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019, 2020 Kevin Ryde
This file is part of MathPlanePath.
MathPlanePath 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.
MathPlanePath 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 MathPlanePath. If not, see <http://www.gnu.org/licenses/>.