3
$\begingroup$

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:

space-filling curve for rectangle of width = 4, height = 4

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?

$\endgroup$
4
  • 2
    $\begingroup$ Do you have a specific space-filling curve in mind? $\endgroup$ Dec 25, 2014 at 23:31
  • $\begingroup$ I want a curve that has the same properties as the Hilbert Curve, except for rectangles. $\endgroup$
    – Viclib
    Dec 25, 2014 at 23:44
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 26, 2014 at 13:25
  • 2
    $\begingroup$ @HendrikJan Care to make (a digest of) this an answer? $\endgroup$
    – Raphael
    Jun 29, 2015 at 17:55

2 Answers 2

1
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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]
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.