# What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?

Suppose that I have a space filling curve over a rectangle of width W and height H. For example, for the rectangle:

W = 4
H = 4


I have the following curve:

Now, given the following coordinate:

X = 1
Y = 2


We can say that its position on the space-filling curve is 7, as it takes 7 steps walking over the curve to reach that tile. Using that logic, we can build a mapping width → height → x → y → index, such as:

spaceFillingIndex(4,4,1,2) = 7


As well as its inverse, width → height → index → (x,y).

spaceFillingCoordinate(4,4,7) = (1,2)


My question is: what is an algorithm that implements spaceFillingIndex, and what is an algorithm that implements spaceFillingCoodinate?

• Do you have a specific space-filling curve in mind? Dec 25, 2014 at 23:31
• I want a curve that has the same properties as the Hilbert Curve, except for rectangles. Dec 25, 2014 at 23:44
• For the regular "square" Hilbert curve, Damn Cool Algorithms explains how both coordinates and indexes can be predicted by building a 4-ary tree by recursively refining the curve. It has some links to code too. For a single point one does not need to construct the complete tree, but only a single path. Dec 26, 2014 at 13:25
• @HendrikJan Care to make (a digest of) this an answer? Jun 29, 2015 at 17:55

I found the math behind the hilbert curve very interesting (generates the space filling coordinates, with index) http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html

Python package refer, https://github.com/galtay/hilbertcurve

for rectangles , you need pseudo Hilbert curve generation https://stackoverflow.com/questions/38463130/hilbert-peano-curve-to-scan-image-of-arbitrary-size

and refer this https://github.com/jakubcerveny/gilbert

There is a very commonly used index formula to map between 2d and 1d:

for x=0; x<width; ++x
for y=0; y<height; ++y
i = x + y * width


One option, is to just run this, store the indices, then use the index when needed (unless you want to generate the whole index on the fly)

For example:

function spaceFillingIndex(width,height,px,py)
// if using base 1 indexes:
i = (px-1) + (py-1) * width
return i

// gives answers in the range [0-15]
spaceFillingIndex(4,4,1,2) = 4


And

function spaceFillingCoordinate(width,height,index)
for x=0; x<width; ++x
for y=0; y<height; ++y
i = x + y * width
if i == index
return (x, y)

spaceFillingCoordinate(4,4,4) = (1,2)


Beware, the order in which the above formula goes through the positions in the 2d array, is not continous in space (it scans column by column, but always "jumping" from the max height to height 0)

However, the general structure still applies.

Additionally, you can add a "cache" for the mapping: iterate through all x,y values within width, height, calculate the index for each of them, and store that in a hash, using x_y as the key

For example:

width_height_map = []

for x=0; x<width; ++x
for y=0; y<height; ++y
i = x + y * width
index_name = x + '_' + y
width_height_map[i] = (x, y)


Then instead of spaceFillingCoordinate having to iterate over the whole data every time, you can just do:

function spaceFillingCoordinate(width,height,index)
return width_height_map[index]