NAME
Math::PlanePath::HIndexing  selfsimilar righttriangle traversal
SYNOPSIS
use Math::PlanePath::HIndexing;
my $path = Math::PlanePath::HIndexing>new;
my ($x, $y) = $path>n_to_xy (123);
DESCRIPTION
This is an infinite integer version of the Hindexing by Rolf Niedermeier, Klaus Reinhardt and Peter Sanders.
"Towards Optimal Locality In Mesh Indexings", Discrete Applied Mathematics, volume 117, March 2002. http://theinf1.informatik.unijena.de/publications/dam01a.pdf
It traverses an octant of the plane by selfsimilar right triangles. Notice the "H" shapes that arise from the backtracking, for example N=8 to N=23, and repeating above it.
 
15  6364 6768 7576 7980 111112 115116 123124 127
               
14  62 6566 69 74 7778 81 110 113114 117 122 125126
       
13  61 5857 70 73 8685 82 109 106105 118 121
             
12  6059 56 7172 87 8483 108107 104 119120
   
11  5152 55 4039 88 9192 99100 103
           
10  50 5354 41 38 8990 93 98 101102
     
9  49 4645 42 37 3433 94 97
         
8  4847 4443 3635 32 9596
 
7  1516 1920 2728 31
       
6  14 1718 21 26 2930
   
5  13 10 9 22 25
     
4  1211 8 2324
 
3  3 4 7
   
2  2 5 6
 
1  1
 
Y=0  0
+
X=0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
The tiling is essentially the same as the Sierpinski curve (see Math::PlanePath::SierpinskiCurve). The following is with two points per triangle. Or equally well it could be thought of with those triangles further divided to have one point each, a little skewed.
++++/
 \  /  \  /
 15 \ 16 19 /20 27\ 28 31 /
  \   /    \    /
 14 \17 18/ 21 26 \29 30 /
 \  /  \  /
+++/
 /  \  /
 13 /10  9 \ 22  25 /
  /    \    /
 12/ 11  8 \23  24/
 /  \  /
+/
 \  /
 3 \ 4  7 /
  \    /
 2 \ 5  6 /
 \  /
+/
 /
 1 /
  /
 0 /
 /
+/
The correspondence to the SierpinskiCurve
is as follows. The 4point verticals like N=0 to N=3 are a Sierpinski horizontal, and the 4point "U" parts like N=4 to N=7 are a Sierpinski vertical. In both cases there's an X,Y transpose and bit of stretching.
3 7
 /
2 12 56 6
 <=> / \   <=> 
1 0 3 4 7 5
 \
0 4
Level Ranges
Counting the initial N=0 to N=7 section as level 1, the X,Y ranges for a given level is
Nlevel = 2*4^level  1
Xmax = 2*2^level  2
Ymax = 2*2^level  1
For example level=3 is N through to Nlevel=2*4^31=127 and X,Y ranging up to Xmax=2*2^32=14 and Xmax=2*2^31=15.
On even Y rows, the N on the X=Y diagonal is found by duplicating each bit in Y except the low zero (which is unchanged). For example Y=10 decimal is 1010 binary, duplicate to binary 1100110 is N=102.
FUNCTIONS
See "FUNCTIONS" in Math::PlanePath for behaviour common to all path classes.
$path = Math::PlanePath::HIndexing>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.
OEIS
Entries in Sloane's Online Encyclopedia of Integer Sequences related to this path include
http://oeis.org/A097110 (etc)
A097110 Y at N=2^k, being successively 2^j1, 2^j
SEE ALSO
Math::PlanePath, Math::PlanePath::SierpinskiCurve
HOME PAGE
http://user42.tuxfamily.org/mathplanepath/index.html
LICENSE
Copyright 2011, 2012, 2013, 2014 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/>.