2

I would like to transform a coordinate pair represented by two double values (x, y) into a Hilbert value. I have found the following implementation (from this link):

/*****************************************************************
 * hilbert_c2i
 * 
 * Convert coordinates of a point on a Hilbert curve to its index.
 * Inputs:
 *  nDims:      Number of coordinates.
 *  nBits:      Number of bits/coordinate.
 *  coord:      Array of n nBits-bit coordinates.
 * Outputs:
 *  index:      Output index value.  nDims*nBits bits.
 * Assumptions:
 *      nDims*nBits <= (sizeof bitmask_t) * (bits_per_byte)
 */
bitmask_t
hilbert_c2i(unsigned nDims, unsigned nBits, bitmask_t const coord[])
{
  if (nDims > 1)
    {
      unsigned const nDimsBits = nDims*nBits;
      bitmask_t index;
      unsigned d;
      bitmask_t coords = 0;
      for (d = nDims; d--; )
    {
      coords <<= nBits;
      coords |= coord[d];
    }

      if (nBits > 1)
    {
      halfmask_t const ndOnes = ones(halfmask_t,nDims);
      halfmask_t const nd1Ones= ndOnes >> 1; /* for adjust_rotation */
      unsigned b = nDimsBits;
      unsigned rotation = 0;
      halfmask_t flipBit = 0;
      bitmask_t const nthbits = ones(bitmask_t,nDimsBits) / ndOnes;
      coords = bitTranspose(nDims, nBits, coords);
      coords ^= coords >> nDims;
      index = 0;
      do
        {
          halfmask_t bits = (coords >> (b-=nDims)) & ndOnes;
          bits = rotateRight(flipBit ^ bits, rotation, nDims);
          index <<= nDims;
          index |= bits;
          flipBit = (halfmask_t)1 << rotation;
          adjust_rotation(rotation,nDims,bits);
        } while (b);
      index ^= nthbits >> 1;
    }
      else
    index = coords;
      for (d = 1; d < nDimsBits; d *= 2)
    index ^= index >> d;
      return index;
    }
  else
    return coord[0];
}

However, this is for integer values as input. How would be the adaptation for my double values?

Anderson Carniel
  • 1,711
  • 2
  • 16
  • 22
  • 2
    If the architecture uses [IEEE 754 Binary64](https://en.wikipedia.org/wiki/IEEE_floating_point#Basic_and_interchange_formats) type for `double`, and the same byte order for `double` as it does for the `uint64_t` integer type, -- and this is the case on e.g. x86-64 architecture (64-bit Intel/AMD) --, and all your `double`s have a finite value, then you can copy the storage of the `double` into an `uint64_t`, and subtract 2⁶³ = 9,223,372,036,854,775,808, and use the result as an unsigned 64-bit integer. This mapping preserves the order of all finite values, and is invertible (back to `double`). – Nominal Animal Mar 29 '17 at 23:39
  • @NominalAnimal Thank you for the suggestion. Therefore, I would do this proposed conversion and call the function without any changing? my double values can be negative too. In addition, I need to get a double value as return too. – Anderson Carniel Mar 29 '17 at 23:50

1 Answers1

0

For anyone wandering, the wikipedia page has a very fast method to compute Hilbert 1D coordinates. I've used Hilbert in multiple programs (I do research on Delaunay Triangulation and we need it to speed-up the process) and I can assure you it's the best one can find.

yakoudbz
  • 903
  • 1
  • 6
  • 14