bulkinsert — Как реализовать z-порядок сортировки для координат для массовой вставки Quad-Tree

Question

bulkinsert — Как реализовать z-порядок сортировки для координат для массовой вставки Quad-Tree

В соответствии с Улучшенные алгоритмы массовой загрузки для Quadtree, сортировка координат в z-порядке перед вставкой приведет к ускорению пакетной вставки QuadTree.

Мне нужна реализация z-порядка в C ++.
У меня есть координаты х, у оба double, Решение здесь, в Википедии для Z-Order-кривых
это отчасти неясно для меня.

РЕДАКТИРОВАТЬ — предположения
Координаты, которые у меня есть, находятся в координатах Google и являются числами с плавающей точкой.
В системе, которую мы сейчас разрабатываем, мы предполагаем, что любой объем (пакет), который будет вставлен, помещается в ОЗУ. Мы не ожидаем необходимости внешних операций сортировки с переключением между диском и памятью.

РЕДАКТИРОВАТЬ 2
Что касается того факта, что Z-порядок работает только для целых чисел, я думаю, что хитрость заключается в умножении на 10, пока все данные не будут целыми числами. После того, как у меня есть то, что способ выполнить Z-порядок на точках?

0

bulkinsert c++quadtree z-order

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Это непроверенный код, вы должны дважды проверить, работает ли он.

Кроме того, этот код почти наверняка не является переносимым и может даже иметь неопределенное поведение. Это, безусловно, поведение, определяемое реализацией, по крайней мере, но оно, вероятно, не определено … Мне бы пришлось более внимательно прочитать правила, касающиеся reinterpret_cast к и от char* знать наверняка.

#include <cstdint>
#include <vector>

uint64_t reinterpretDoubleAsUInt(double d) {
int const doubleSize = sizeof(double);
char* array = reinterpret_cast<char*>(&d);
uint64_t result = 0;
for (auto i = 0; i < doubleSize; ++i) {
result += (uint64_t)array[i] << (8*i);
}

return result;
}

bool lessThanZOrderDouble(std::vector<double> const& a, std::vector<double> const& b) {
uint64_t j = 0;
uint64_t x = 0;
if (a.size() != b.size() || a.size() == 0) {
throw std::exception();
}

int dimensions = a.size();

for (auto i = 0; i < dimensions; ++i) {
auto y = reinterpretDoubleAsUInt(a[i]) ^ reinterpretDoubleAsUInt(b[i]);
if (x < y && x < (x ^ y)) {
j = i;
x = y;
}
}
return (a[j] - b[j]) > 0;
}

int main() {
// blank for compilation's sake
}

1