NAME

Path::Hilbert - A no-frills converter between 1D and 2D spaces using the Hilbert curve

SYNOPSIS

use Path::Hilbert;
my ($x, $y) = d2xy(16, 127);
my $d = xy2d(16, $x, $y);
die unless $d == 127;

my $space = Path::Hilbert->new(16);
my ($u, $v) = $space->d2xy(127);
my $t = $space->xy2d($u, $v);
die unless $t == 127;

Description

See Wikipedia for a description of the Hilbert curve, and why it's a good idea.

Most (all?) of the existing CPAN modules for dealing with Hilbert curves state "only works for $foo data", "optimized for $foo situations", or "designed to work as part of the $foo framework".

This module is based directly on the example algorithm given on Wikipedia, except it is not subject to the strict limitation of "proper" Hilbert curves, which is that the side-length $n MUST be a non-negative integer power of 2.

If you supply an "invalid but sane" side length (i.e. any positive number), be fore-warned that you'll get a non-integer answer. Unfortunately, I haven't yet worked out how to make this particular algorithm work with non-integer inputs for $d, or ($x, $y), so if you supply such, they'll be rounded to the nearest integer before being fed into the algorithm. So far, I have not found a practical real-world use-case where the rounding-error is significant -- except perhaps in the case of very small (single digit or less) side lengths, but I hereby advise you to pre- and post-scale the arguments and return values by some sane amount as the best workaround.

Function-Oriented Interface

($X, $Y) = d2xy($SIDE, $INDEX)

Returns the X and Y coordinates (each in the range 0 .. n - 1) of the supplied INDEX (in the range 0 .. SIDE ** 2 - 1), where SIDE itself is an integer power of 2.

$INDEX = xy2d($SIDE, $X, $Y)

Returns the INDEX (in the range 0 .. SIDE ** 2 - 1) of the point corresponding to the supplied X and Y coordinates (each in the range 0 .. n - 1), where SIDE itself is an integer power of 2.

Object-Oriented Interface

$object = Path::Hilbert->new(SIDE)

Create a new Path::Hilbert object with the specified SIDE (which must be an integer power of 2).

($X, $Y) = $object->d2xy($INDEX)

Returns the X and Y coordinates (each in the range 0 .. n - 1) of the supplied INDEX (in the range 0 .. SIDE ** 2 - 1), where SIDE was provided via new().

$INDEX = $object->xy2d($X, $Y)

Returns the INDEX (in the range 0 .. SIDE ** 2 - 1) of the point corresponding to the supplied X and Y coordinates (each in the range 0 .. n - 1), where SIDE was provided via new().

CAVEATS

If your platform has $n bit integers, things will go badly if you try a side length longer than 2 ** ($n / 2). If you need enormous Hilbert spaces, you should try Path::Hilbert::BigInt, which uses Math::BigInt instead of the native integer support for your platform.

BUGS

Please let me know via the CPAN RT if you find any algorithmic defects. I'm well aware that there are a number of opportunities to speed it up.

TODO

Speed it up. XS? Memoization?

AUTHOR

PWBENNETT <paul.w.bennett@gmail.com>

LICENSE

GNU LGPL 3.0 or newer.