带有浮点数的二维点的莫顿指数

Question

我有一个看起来像这样的 2D 点：

class Point
{
    float m_x, m_y;

public:

    int mortonIndex()
    {
        // what would go here?
    }
};

我知道如何处理整数，但我需要使用浮点数。我还想避免缩放任何特定的网格大小。

维基百科上的相关页面：

莫顿指数，或 Z 阶曲线

Answer 1

有两种看待这个问题的方法：

• “float”是一个 256 位数字（或者类似地，“double”是一个 2100 位数字，[此处][1] 实现）。
• “float”是一个奇怪的 32 位整数。

我会使用后者，因为它更容易实现。

此方法利用了 IEEE

float

最初设计为与旧的纯整数数据库引擎兼容的事实，允许它们将浮点数视为 1 补码整数。

更准确地说，在 1 补码意义上，浮点值的排序遵循相同宽度的整数的排序（事实上，直接将 1 添加到双关浮点数将为您提供具有更大绝对量值的相邻值**）。

class Point
{
    float m_x, m_y;

    // This assert is not correct when the floating point model
    // is not IEEE-compliant, float is not 32-bit, or both.
    //
    // Such things are hard to find, so we'll just assume
    // mostly-sane hardware.
    //
    static_assert(
        (sizeof(int) == sizeof(float)) &&
        (sizeof(int)*CHAR_BIT == 32) &&
        (sizeof(long long)*CHAR_BIT == 64),
        "We need 32-bit ints and floats, and 64-bit long longs!"
        );

public:

    // So we don't lose any information, we need 2x the width.
    // After all, we're cramming two 32-bit numbers into a single value.
    // Lossiness here would mean a container would need to implement
    // a binning strategy.
    //
    // Higher dimensions would require an array, obviously.
    //
    // Also, we're not going to modify the point, so make this a const routine.
    //
    long long mortonIndex() const
    {
        // Pun the x and y coordinates as integers: Just re-interpret the bits.
        //
        auto ix = reinterpret_cast<const unsigned &>(this->m_x);
        auto iy = reinterpret_cast<const unsigned &>(this->m_y);

        // Since we're assuming 2s complement arithmetic (99.99% of hardware today),
        // we'll need to convert these raw integer-punned floats into
        // their corresponding integer "indices".

        // Smear their sign bits into these for twiddling below.
        //
        const auto ixs = static_cast<int>(ix) >> 31;
        const auto iys = static_cast<int>(iy) >> 31;

        // This is a combination of a fast absolute value and a bias.
        //
        // We need to adjust the values so -FLT_MAX is close to 0.
        //
        ix = (((ix & 0x7FFFFFFFL) ^ ixs) - ixs) + 0x7FFFFFFFL;
        iy = (((iy & 0x7FFFFFFFL) ^ iys) - iys) + 0x7FFFFFFFL;

        // Now we have -FLT_MAX close to 0, and FLT_MAX close to UINT_MAX,
        // with everything else in-between.
        //
        // To make this easy, we'll work with x and y as 64-bit integers.
        //
        long long xx = ix;
        long long yy = iy;

        // Dilate and combine as usual...

        xx = (xx | (xx << 16)) & 0x0000ffff0000ffffLL;
        yy = (yy | (yy << 16)) & 0x0000ffff0000ffffLL;

        xx = (xx | (xx <<  8)) & 0x00ff00ff00ff00ffLL;
        yy = (yy | (yy <<  8)) & 0x00ff00ff00ff00ffLL;

        xx = (xx | (xx <<  4)) & 0x0f0f0f0f0f0f0f0fLL;
        yy = (yy | (yy <<  4)) & 0x0f0f0f0f0f0f0f0fLL;

        xx = (xx | (xx <<  2)) & 0x3333333333333333LL;
        yy = (yy | (yy <<  2)) & 0x3333333333333333LL;

        xx = (xx | (xx <<  1)) & 0x5555555555555555LL;
        yy = (yy | (yy <<  1)) & 0x5555555555555555LL;

        return xx | (yy << 1);
    }
};

请注意，生成的曲线的顶点与 2D 浮点空间中的位置具有相同的分布。

如果您打算将其与磁盘结构一起使用，这可能是一个问题，因为在坐标轴或原点附近进行聚类可能会导致范围查询跨越它们附近的大量框。否则，IMO，它是生成统一索引的一个相当高性能的替代方案（并且它没有分支！）。

**对于无穷大和 NaN 需要特殊处理，但你明白了。