Construct Hilbert Curves.
Project description
Introduction
This is a package to convert between one dimensional distance along a Hilbert curve, h, and ndimensional points, (x_0, x_1, ... x_n1). 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 ndimensional 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).
Quickstart
Install the package with pip,
pip install hilbertcurve
You can calculate points given distances along a hilbert curve,
>>> from hilbertcurve.hilbertcurve import HilbertCurve
>>> p=1; n=2
>>> hilbert_curve = HilbertCurve(p, n)
>>> distances = list(range(4))
>>> points = hilbert_curve.points_from_distances(distances)
>>> for point, dist in zip(points, distances):
>>> print(f'point(h={dist}) = {point}')
point(h=0) = [0, 0]
point(h=1) = [0, 1]
point(h=2) = [1, 1]
point(h=3) = [1, 0]
You can also calculate distances along a hilbert curve given points,
>>> points = [[0,0], [0,1], [1,1], [1,0]]
>>> distances = hilbert_curve.distances_from_points(points)
>>> for point, dist in zip(points, distances):
>>> print(f'distance(x={point}) = {dist}')
distance(x=[0, 0]) = 0
distance(x=[0, 1]) = 1
distance(x=[1, 1]) = 2
distance(x=[1, 0]) = 3
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 1d numpy arrays. Arguments that are type hinted with Iterable[Iterable[int]] have been tested with list of lists, tuples of tuples, and 2d 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,
>>> 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
Multiprocessing
You can now take advantage of multiple processes to speed up calculations by using the n_procs keyword argument when creating an instance of HilbertCurve.
n_procs (int): number of processes to use
0 = dont use multiprocessing
1 = use all available processes
any other positive integer = number of processes to use
A value of 0 will completely avoid using the multiprocessing module while a value of 1 will use the multiprocessing module but with a single process. If you want to take advantage of every thread on your computer use the value 1 and if you want something in the middle use a value between 1 and the number of threads on your computer. A concrete example starting with the code block above is,
>>> from hilbertcurve.hilbertcurve import HilbertCurve
>>> p=1; n=2
>>> hilbert_curve = HilbertCurve(p, n, n_procs=1)
>>> num_points = 100_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)
The following methods are able to use multiple cores.
points_from_distances(distances: Iterable[int], match_type: bool=False) > Iterable[Iterable[int]]
distances_from_points(points: Iterable[Iterable[int]], match_type: bool=False) > Iterable[int]
(Absurdly) Large Integers
Due to the magic of arbitrarily large integers in Python, these calculations can be done with … well … arbitrarily large integers!
>>> p = 512; n = 10
>>> hilbert_curve = HilbertCurve(p, n)
>>> ii = 123456789101112131415161718192021222324252627282930
>>> point = hilbert_curve.points_from_distances([ii])[0]
>>> print(f'point = {point}')
point = [121075, 67332, 67326, 108879, 26637, 43346, 23848, 1551, 68130, 84004]
The calculations above represent the 512th iteration of the Hilbert curve in 10 dimensions. The maximum value along any coordinate axis is an integer with 155 digits and the maximum distance along the curve is an integer with 1542 digits. For comparison, an estimate of the number of atoms in the observable universe is 10^{82} (i.e. an integer with 83 digits).
Visuals
An animation of the same case in 3D 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.
Reference
This module is based on the C code provided in the 2004 article “Programming the Hilbert Curve” by John Skilling,
I was also helped by the discussion in the following stackoverflow post,
which points out a typo in the source code of the paper. The Skilling code provides two functions TransposetoAxes and AxestoTranspose. In this case, Transpose refers to a specific packing of the integer that represents distance along the Hilbert curve (see below for details) and Axes refer to the ndimensional coordinates. Below is an excerpt from the documentation of Skilling’s code,
//+++++++++++++++++++++++++++ PUBLICDOMAIN SOFTWARE ++++++++++++++++++++++++++ // Functions: TransposetoAxes AxestoTranspose // Purpose: Transform inplace between Hilbert transpose and geometrical axes // Example: b=5 bits for each of n=3 coordinates. // 15bit Hilbert integer = A B C D E F G H I J K L M N O is stored // as its Transpose // X[0] = A D G J M X[2] // X[1] = B E H K N <>  /X[1] // X[2] = C F I L O axes / // high low 0 X[0] // Axes are stored conveniently as bbit integers. // Author: John Skilling 20 Apr 2001 to 11 Oct 2003
Change Log
Version 2.0
Version 2.0 introduces some breaking changes.
API Changes
Previous versions transformed a single distance to a vector or a single vector to a distance.
coordinates_from_distance(self, h: int) > List[int]
distance_from_coordinates(self, x_in: List[int]) > int
In version 2.0 coordinates > point(s) and we add methods to handle multiple distances or multiple points. The match_type kwarg forces the output type to match the input type and all functions can handle tuples, lists, and ndarrays.
point_from_distance(self, distance: int) > Iterable[int]
points_from_distances(self, distances: Iterable[int], match_type: bool=False) > Iterable[Iterable[int]]
distance_from_point(self, point: Iterable[int]) > int
distances_from_points(self, points: Iterable[Iterable[int]], match_type: bool=False) > Iterable[int]
Multiprocessing
The methods that handle multiple distances or multiple points can take advantage of multiple cores. You can control this behavior using the n_procs kwarg when you create an instance of HilbertCurve.
Project details
Release history Release notifications  RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for hilbertcurve2.0.5py3noneany.whl
Algorithm  Hash digest  

SHA256  dbaad510237d3cd4355c189f00e8dbe66a9e66e03af37f9d3f257799292da363 

MD5  8d37df3c7697ad8e38a3295583f8fadc 

BLAKE2b256  9aceb5b18c87a6f02057fe5b2d0638cac0d097de983f560a53213d94e6352907 