NAME

Math::PlanePath::MathImageAR2W2Curve -- 2x2 self-similar of four pattern parts

SYNOPSIS

use Math::PlanePath::MathImageAR2W2Curve;
my $path = Math::PlanePath::MathImageAR2W2Curve->new;
my ($x, $y) = $path->n_to_xy (123);

DESCRIPTION

In progress ...

This is an integer version of the AR2W2 curve by Asano, Ranjan, Roos, Welzl and Widmayer.

                                     | 
  7     42--43--44  47--48--49  62--63   
          \      |   |       |   |     
  6     40--41  45--46  51--50  61--60 
         |               |           | 
  5     39  36--35--34  52  55--56  59 
         |   |    /      |   |   |   | 
  4     38--37  33--32  53--54  57--58 
                      \                
  3      6-- 7-- 8  10  31  28--27--26 
         |       |/  |   |   |       | 
  2      5-- 4   9  11  30--29  24--25 
             |       |           |     
  1      2-- 3  13--12  17--18  23--22 
          \      |       |   |       | 
Y=0 ->   0-- 1  14--15--16  19--20--21 
      
        X=0  1   2   3   4   5   6   7 

It makes a 2x2 expanding pattern with a mixture of "U" and "Z" shapes. The mixture is designed to improve some locality measures.

There's four base patterns A to D. A2 is a reversal of A1, and B2 a reversal of B1, etc.

      C1---B2             C2   D1
A1       \          A2     | \  |
      D2---B1             B1   B2
                      
      C2---B1             B2---C1
B1     |    |       B2     |    |
      D1   B2             B1   D2
                      
      B1---A1             A2---B2
C1     |    |       C2     |    |
      A2   B2             B1   A1
                      
       A2---C2             C1---A1
D1      |    |       D2     |    |
       D1   A2             A1   D2
     trans
                        

The starting pattern is the A1 "Z" shape and above that D2. Notice the starting sub-part of D2 is A1 and in turn the starting sub-part of A1 is D2, so those two alternate at progressively higher levels. The sub-parts of those then reach all of the others, and rotated in four directions.

The curve is conceived by the authors as going downwards into ever-smaller sub-parts and for that any of the patterns can be the top-level start. But for the expanding outwards version here the start must occur as the first part of the pattern above it, which means the A1/D2 pair, or alternatively the D1/D1trans which is its own start with a transpose.

Other parts can't be the N=0 starting point. B2, C1 and C2 aren't the start of anything, so if one of them was the initial N=0 to N=3 then there'd be nothing which could be above. A2 is the start of C1, but nothing there. And B1 is the start of C2, B2 or A2, but then they don't lead anywhere.

FUNCTIONS

See "FUNCTIONS" in Math::PlanePath for the behaviour common to all path classes.

$path = Math::PlanePath::MathImageAR2W2Curve->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.

SEE ALSO

Math::PlanePath, Math::PlanePath::HilbertCurve, Math::PlanePath::ZOrderCurve

Asano, Ranjan, Roos, Welzl and Widmayer "Space-Filling Curves and Their Use in the Design of Geometric Data Structures", Theoretical Computer Science, 181(1):3-15, 1997. And LATIN'95 Theoretical Informatics which is at Google Books

http://books.google.com/books?isbn=3540591753