Как рассчитать индекс Гильберта по двойным координатам?

Question

Я хотел бы преобразовать пару координат, представленную двумя двойными значениями (x, y), в значение Гильберта. Я нашел следующую реализацию ( по этой ссылке):

/*****************************************************************
 * 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];
}

Однако это для целочисленных значений в качестве входных данных. Как бы адаптация к моим двойным ценностям?

Answer 1

Для тех, кто бродит, на странице википедии есть очень быстрый метод вычисления координат Гильберта 1D. Я использовал Гильберта в нескольких программах (я занимаюсь исследованием триангуляции Делоне, и нам это нужно для ускорения процесса), и я могу заверить вас, что это лучшее, что можно найти.