Hilbert Curve Library

.. image:: https://travis-ci.com/galtay/hilbertcurve.svg?branch=develop
:target: https://travis-ci.com/galtay/hilbertcurve

.. contents:: Table of Contents
:depth: 2

============
Introduction

This is a package to convert between one dimensional distance along a
Hilbert curve_, h, and n-dimensional points,
(x_0, x_1, ... x_n-1). There are two important parameters,

• n -- the number of dimensions (must be > 0)
• p -- the number of iterations used in constructing the Hilbert curve (must be > 0)

We consider an n-dimensional hypercube_ of side length 2^p.
This hypercube contains 2^{n p} unit hypercubes (2^p along
each dimension). The number of unit hypercubes determine the possible
discrete distances along the Hilbert curve (indexed from 0 to
2^{n p} - 1).

=========================
Inputs and Outputs

The HilbertCurve class has four main public methods.

• point_from_distance(distance: int) -> Iterable[int]
• points_from_distances(distances: Iterable[int], match_type: bool=False) -> Iterable[Iterable[int]]
• distance_from_point(point: Iterable[int]) -> int
• distances_from_points(points: Iterable[Iterable[int]], match_type: bool=False) -> Iterable[int]

Arguments that are type hinted with Iterable[int] have been tested with lists, tuples, and 1-d numpy arrays.
Arguments that are type hinted with Iterable[Iterable[int]] have been tested with list of lists, tuples of tuples, and 2-d numpy arrays with shape (num_points, num_dimensions). The match_type key word argument forces the output iterable to match the type of the input iterable.

The HilbertCurve class also contains some useful metadata derived from the inputs p and n. For instance, you can construct a numpy array of random points on the hilbert curve and calculate their distances in the following way,

.. code-block:: python

from hilbertcurve.hilbertcurve import HilbertCurve
p=1; n=2
hilbert_curve = HilbertCurve(p, n)
num_points = 10_000
points = np.random.randint(
low=0,
high=hilbert_curve.max_x + 1,
size=(num_points, hilbert_curve.n)
)
distances = hilbert_curve.distances_from_points(points)
type(distances)

list

distances = hilbert_curve.distances_from_points(points, match_type=True)
type(distances)

numpy.ndarray

=======
Visuals

.. figure:: https://raw.githubusercontent.com/galtay/hilbertcurve/main/n2_p3.png

The figure above shows the first three iterations of the Hilbert
curve in two (n=2) dimensions. The p=1 iteration is shown
in red, p=2 in blue, and p=3 in black.
For the p=3 iteration, distances, h, along the curve are
labeled from 0 to 63 (i.e. from 0 to 2^{n p}-1). This package
provides methods to translate between n-dimensional points and one
dimensional distance. For example, between (x_0=4, x_1=6) and
h=36. Note that the p=1 and p=2 iterations have been
scaled and translated to the coordinate system of the p=3 iteration.

An animation of the same case in 3-D is available on YouTube. To watch the video,
click the link below. Once the YouTube video loads, you can right click on it and
turn "Loop" on to watch the curve rotate continuously.

.. figure:: https://img.youtube.com/vi/TfJEJidwkBQ/0.jpg

3-D Hilbert Curve Animation https://www.youtube.com/watch?v=TfJEJidwkBQ