c++ - Morton index from 2D point with floats -

c++ - Morton index from 2D point with floats -

i have 2d point looks this:

class point { float m_x, m_y; public: int mortonindex() { // go here? } };

i know integers, need utilize floats. want avoid scaling particular grid size.

related page on wikipedia:

morton index, or z order curve

there 2 ways of looking @ this:

`float` beingness 256-bit number, (or similarly, `double` 2100-bit number, implemented [here][1]). `float` beingness weird 32-bit integer.

i'll utilize latter, it's easier implement.

this approach takes advantage of fact ieee floats designed compatible old integer-only database engines, allowing them treat floating point numbers 1s complement integers.

more precisely, in 1s complement sense, ordering of floating point values respects of integers of same width (in fact, straight adding 1 punned float give adjacent value larger absolute magnitude**).

class point { float m_x, m_y; // assert not right when floating point model // not ieee-compliant, float not 32-bit, or both. // // such things hard find, we'll 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 , floats, , 64-bit long longs!" ); public: // don't lose information, need 2x width. // after all, we're cramming 2 32-bit numbers single value. // lossiness here mean container need implement // binning strategy. // // higher dimensions require array, obviously. // // also, we're not going modify point, create const routine. // long long mortonindex() const { // pun x , y coordinates integers: re-interpret 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 convert these raw integer-punned floats // corresponding integer "indices". // smear sign bits these twiddling below. // const auto ixs = static_cast<int>(ix) >> 31; const auto iys = static_cast<int>(iy) >> 31; // combination of fast absolute value , bias. // // need adjust values -flt_max close 0. // ix = (((ix & 0x7fffffffl) ^ ixs) - ixs) + 0x7fffffffl; iy = (((iy & 0x7fffffffl) ^ iys) - iys) + 0x7fffffffl; // have -flt_max close 0, , flt_max close uint_max, // else in-between. // // create easy, we'll work x , y 64-bit integers. // long long xx = ix; long long yy = iy; // dilate , combine 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; homecoming xx | (yy << 1); } };

note vertices of resulting curve have same distribution positions in 2d floating point space.

this can problem if intend utilize on-disk structure, clustering near coordinate axes or origin can cause range queries cross big number of boxes near them. otherwise, imo, reasonably performant alternative generating uniform indices (and devoid of branches!).

**special handling needed infinities , nan, idea.

c++ algorithm