/ 
Math-PlanePath-85
River stage one • 3 direct dependents • 4 total dependents
/ Math::PlanePath::HIndexing

NAME

Math::PlanePath::HIndexing -- self-similar right-triangle 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 H-indexing by Rolf Niedermeier, Klaus Reinhardt and Peter Sanders.

It traverses an octant of the plane by self-similar right triangles. Notice the "H" shapes that arise from the backtracking, for example N=8 to N=23, and repeating above it.

    |                                                           |
 15 |  63--64  67--68  75--76  79--80 111-112 115-116 123-124 127
    |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 14 |  62  65--66  69  74  77--78  81 110 113-114 117 122 125-126
    |   |           |   |           |   |           |   |
 13 |  61  58--57  70  73  86--85  82 109 106-105 118 121
    |   |   |   |   |   |   |   |   |   |   |   |   |   |
 12 |  60--59  56  71--72  87  84--83 108-107 104 119-120
    |           |           |                   |
 11 |  51--52  55  40--39  88  91--92  99-100 103
    |   |   |   |   |   |   |   |   |   |   |   |
 10 |  50  53--54  41  38  89--90  93  98 101-102
    |   |           |   |           |   |
  9 |  49  46--45  42  37  34--33  94  97
    |   |   |   |   |   |   |   |   |   |
  8 |  48--47  44--43  36--35  32  95--96
    |                           |
  7 |  15--16  19--20  27--28  31
    |   |   |   |   |   |   |   |
  6 |  14  17--18  21  26  29--30
    |   |           |   |
  5 |  13  10-- 9  22  25
    |   |   |   |   |   |
  4 |  12--11   8  23--24
    |           |
  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 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 4-point verticals like N=0 to N=3 are a Sierpinski horizontal, and the 4-point "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         1--2             5--6       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^3-1=127 and X,Y ranging up to Xmax=2*2^3-2=14 and Xmax=2*2^3-1=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.

SEE ALSO

Math::PlanePath, Math::PlanePath::SierpinskiCurve

Rolf Niedermeier, Klaus Reinhardt and Peter Sanders, "Towards Optimal Locality In Mesh Indexings", Discrete Applied Mathematics, vol 117, March 2002.

http://theinf1.informatik.uni-jena.de/publications/dam01a.pdf

HOME PAGE

http://user42.tuxfamily.org/math-planepath/index.html

LICENSE

Copyright 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/>.