Эвристика для сортировки массива точек 2D/3D по их взаимному расстоянию

Question

Рассмотрим массив точек в 2D, 3D, (4D ...) пространстве (например, узлы unstructured mesh). Первоначально индекс точки в массиве не связан с его положением в пространстве. В простом случае предположим, что я уже знаю график ближайшего соседства.

Я бы хотел, чтобы некоторые эвристики увеличивали вероятность того, что две точки, близкие друг к другу в пространстве, будут иметь аналогичный индекс (будет близким по массиву).

Я понимаю, что точное решение очень сложно (возможно, похоже на Travelling salesman problem), но мне не нужно точное решение, просто то, что увеличивает вероятность.

Мои идеи по решению:

некоторые наивным решение было бы как:

1. for each point "i" compute fitness E_i given by sum of distances in array (i.e. index-wise) from its spatial neighbors (i.e. space-wise) 
    E_i = -Sum_k (abs(index(i)-index(k))) 
    where "k" are spatial nearest neighbors of "i" 
2. for pairs of points (i,j) which have low fitness (E_i,E_j) 
    try to swap them, 
    if fitness improves, accept 

но детальное осуществление и его оптимизация производительности не так ясно.

Другое решение, которое не нуждается в предвычисленными ближайших соседей будут основаны на некоторых Locality-sensitive_hashing

Я думаю, что это может быть весьма распространенной проблемой, и могут существовать хорошие решения, я не хочу, чтобы изобретать колесо ,

Применение:

• улучшение кэш местность, учитывая, что доступ к памяти часто узкий граф-обход
• это может ускорить интерполяцию неструктурированной сетки, более конкретно искать узлы, которые находятся рядом с smaple (например, центры радиально-базисной функции).

Answer 1

Я бы сказал, что space filling curves (SPC) - это стандартное решение для сопоставления близости в пространстве с линейным порядком. Наиболее распространенными являются Hilbert-curves и z-curves (Morton order).

Кривые Гильберта имеют наилучшее приближение, но их несколько дороже рассчитать. Z-порядок все еще имеет хорошее сопоставление близости, но его очень легко вычислить. Для z-упорядочения достаточно чередовать биты каждого измерения. Предполагая целочисленные значения, если у вас есть 64-битная трехмерная точка (x, y, z), значение z равно $ x_0, y_0, z_0, x_1, y_1, z_1, ... x_63, y_63, z_63 $, т.е. 192 бит, состоящий из первого бита каждого измерения, за которым следует второй бит каждого измерения и т. д. Если ваш массив упорядочен в соответствии с этим значением z, то точки, близкие по пространству, равны обычно также закрываются в массиве.

Here приведены примеры функций, которые чередуют (merge) значения в г-значение (nBitsPerValue, как правило, 32 или 64):

public static long[] mergeLong(final int nBitsPerValue, long[] src) { 
    final int DIM = src.length; 
    int intArrayLen = (src.length*nBitsPerValue+63) >>> 6; 
    long[] trg = new long[intArrayLen]; 

    long maskSrc = 1L << (nBitsPerValue-1); 
    long maskTrg = 0x8000000000000000L; 
    int srcPos = 0; 
    int trgPos = 0; 
    for (int j = 0; j < nBitsPerValue*DIM; j++) { 
     if ((src[srcPos] & maskSrc) != 0) { 
      trg[trgPos] |= maskTrg; 
     } else { 
      trg[trgPos] &= ~maskTrg; 
     } 
     maskTrg >>>= 1; 
     if (maskTrg == 0) { 
      maskTrg = 0x8000000000000000L; 
      trgPos++; 
     } 
     if (++srcPos == DIM) { 
      srcPos = 0; 
      maskSrc >>>= 1; 
     } 
    } 
    return trg; 
} 

Вы можете также чередовать биты значений с плавающей точкой (если закодированные с IEEE 754, поскольку они обычно находятся на стандартных компьютерах), но это приводит к неевклидовым свойствам расстояния. Возможно, вам придется сначала преобразовать отрицательные значения, см. here, раздел 2.3.

EDIT Два ответ на вопросы из комментариев:

1) Я понимаю, как сделать заполнение пространства кривым для регулярной прямоугольной сетки. Однако, если я случайно разместил плавающие точек, несколько точек могут отображаться в одну ячейку. Будет ли этот алгоритм работать в этом случае?

Существует несколько способов использования значений с плавающей запятой (FP). Самое простое - преобразовать их в целочисленные значения, умножив их на большую константу. Например, умножьте все на 10^6, чтобы сохранить 6-значную точность.

Другой способ - использовать представление bitlevel значения FP, чтобы превратить его в целое число. Это имеет то преимущество, что точность не теряется, и вам не нужно определять константу умножения. Недостатком является то, что метрика евклидова расстояния больше не работает.

Он работает следующим образом. Фокус в том, что значения с плавающей запятой не имеют бесконечной точности, но ограничены до 64 бит. Следовательно, они автоматически образуют сетку. Разница с целыми значениями заключается в том, что значения с плавающей запятой не образуют квадратичную сетку, а прямоугольную сетку, где прямоугольники становятся больше с увеличением расстояния от (0,0). Размер сетки определяется тем, насколько точность доступна в данной точке. Близко к (0,0) точность (= grid_size) равна 10^-28, близкая к (1,1), она равна 10^-16 см. here. Эта искаженная сетка по-прежнему имеет сопоставление близости, но расстояния больше не евклидова.

Вот код, чтобы сделать преобразование (Java, взятый из here, в C++ вы можете просто закиньте float к int):

public static long toSortableLong(double value) { 
    long r = Double.doubleToRawLongBits(value); 
    return (r >= 0) ? r : r^0x7FFFFFFFFFFFFFFFL; 
} 

public static double toDouble(long value) { 
    return Double.longBitsToDouble(value >= 0.0 ? value : value^0x7FFFFFFFFFFFFFFFL); 
} 

Эти преобразования сохранить порядок преобразованных значений, то есть для каждого два значения FP, результирующие целые числа имеют одинаковый порядок по отношению к <,>, =. Неевклидовое поведение вызвано показателем, который закодирован в битовой строке. Как упоминалось выше, это также обсуждается here, раздел 2.3, однако код немного менее оптимизирован.

2) Есть ли какой-нибудь алгоритм, как сделать итеративное обновление такого пространства кривая заполнения, если мои точки перемещаются в пространстве? (То есть без переназначения весь массив каждый раз) кривой наполнения

Пространство накладывает определенный порядок, так что для каждого множества точек есть только один действительный порядок. Если точка перемещается, ее необходимо повторно вставить в новую позицию, определяемую значением z.

Хорошей новостью является то, что небольшое движение, вероятно, означает, что точка может часто оставаться в одной и той же «области» вашего массива. Поэтому, если вы действительно используете фиксированный массив, вам нужно только сдвинуть его мелкие части.

Если у вас много движущихся объектов, а массив - громоздкий, вы можете захотеть изучить «индексы движущихся объектов» (MX-CIF-quadtree и т. Д.). Я лично могу рекомендовать свои собственные PH-Tree. Это своего рода побитовая радикс-квадри, которая использует z-кривую для внутреннего упорядочения. Это довольно эффективно для обновлений (и других операций). Тем не менее, я обычно рекомендую его только для больших наборов данных, для небольших наборов данных простая квадтрия обычно достаточно хороша.

Answer 2

Проблема, которую вы пытаетесь решить, имеет смысл, если задана точка p и ее NN q, то верно, что NN q является p.

Это не тривиально, так как, например, две точки могут представлять позиции в ландшафте, поэтому одна точка может быть высокой в ​​горах, поэтому переход от низа до горы стоит больше, чем наоборот (от горы до дна). Поэтому убедитесь, что вы проверяете, что это не ваше дело.

---

С TilmannZ уже предложил решение, я хотел бы подчеркнуть на LSH вы упомянули. Я бы не выберите, что ваши точки лежат в действительно низкоразмерных пространствах, это даже не 100, так зачем использовать LSH?

Я бы выбрал для CGAL алгоритм на этом случае, например 2D NNS, или даже простой kd-tree. И если скорость критическая, но пространства нет, то почему бы не пойти на quadtree (октет в 3D)? Я построил один, он не будет превышать 10 измерений в 8 ГБ оперативной памяти.

Однако, если вы чувствуете, что ваши данные могут принадлежать в более высокой размерности пространства в будущем, то я предложил бы использовать:

1. LSH от Андони, действительно крутой парень.
2. FLANN, который предлагает другой подход.
3. kd-GeRaF, который разработан мной.