hilbert_curve.py

"""
Adapts C implementation shown at 
https://en.wikipedia.org/wiki/Hilbert_curve
(2018-12-19)
into Python.
"""

import sys
import numpy as np


def xy2d(n: int, x: int, y: int) -> int:
    """
    converts (x,y) to d

    :param n: dimension of 2-d space side (power of 2)
    :param x: x-coordinate of 2-d point
    :param y: y-coordinate of 2-d point
    :return: d is returned
    """
    d = 0
    s = n // 2
    while s > 0:
        rx = (x & s) > 0
        ry = (y & s) > 0
        d += s * s * ((3 * rx) ^ ry)
        x, y = rot(s, x, y, rx, ry)
        s //= 2
    return d


def d2xy(n: int, d: int):
    """
    converts d to (x,y)

    :param n: dimension of 2-d space side (power of 2)
    :param d: the 'distance' coordinate (1-d index)
    :return: x,y is returned as a tuple
    """
    t = d
    x = y = 0
    s = 1
    while s < n:
        rx = 1 & (t // 2)
        ry = 1 & (t ^ rx)
        x, y = rot(s, x, y, rx, ry)
        x += s * rx
        y += s * ry
        t //= 4
        s *= 2
    return (x, y)


def rot(n: int, x: int, y: int, rx: int, ry: int):
    """
    rotate/flip a quadrant appropriately
    """
    if ry == 0:
        if rx == 1:
            x = n - 1 - x
            y = n - 1 - y

        # Swap x and y
        x, y = y, x
    return (x, y)


if __name__ == "__main__":
    print("This script isn't meant to run stand-alone.", file=sys.stderr)
    sys.exit(1)