Нахождение расстояния до ближайшей точки в облаке точек на равномерной сетке

Question

У меня есть 3D-сетка размером AxBxC с равным расстоянием d между точками в сетке. Учитывая количество точек, каков наилучший способ определения расстояния до ближайшей точки для каждой точки сетки (каждая точка сетки должна содержать расстояние до ближайшей точки в облаке точек) с учетом следующих предположений?

Предположим, что A, B и C довольно большие по отношению к d, давая сетку, возможно, 500x500x500 и что будет около 1 миллиона точек.

Также предположим, что если расстояние до ближайшей точки превышает расстояние D, нас не волнует расстояние до ближайшей точки, и его можно смело установить на некоторое большое число (D может быть от 2 до 10 раз d)

Поскольку будет множество точек сетки и точек для поиска, простое исчерпывающее:

for each grid point:
   for each point:
     if distance between points < minDistance:
       minDistance = distance between points

не является хорошей альтернативой.

Я думал о том, чтобы сделать что-то вроде:

create a container of size A*B*C where each element holds a container of points
for each point:
  define indexX = round((point position x - grid min position x)/d)
  // same for y and z
  add the point to the correct index of the container

for each grid point:
  search the container of that grid point and find the closest point
  if no points in container and D > 0.5d:
    search the 26 container indices nearest to the grid point for a closest point
  .. continue with next layer until a point is found or the distance to that layer 
        is greater than D

В основном: поместите точки в ведра и выполните радиальный поиск наружу, пока точки не будут найдены для каждой точки сетки. Это хороший способ решения проблемы, или есть лучшие / более быстрые способы? Решение, которое подходит для распараллеливания, является предпочтительным.

Answer 1

На самом деле, я думаю, у меня есть лучший путь, так как количество точек сетки намного больше, чем количество точек выборки. Пусть | Сетка | = N, | Образцы | = M, тогда алгоритмы поиска ближайших соседей будут чем-то вроде O (N lg M), так как вам нужно искать все N точек сетки, и каждый поиск (в лучшем случае) O (lg M).

Вместо этого переберите точки выборки. Сохраните для каждой точки сетки ближайшую найденную точку выборки. Для каждой точки выборки просто проверьте все точки сетки на расстоянии D от образца, чтобы увидеть, находится ли текущий образец ближе, чем какие-либо ранее обработанные образцы.

Тогда время работы O (N + (D / d) ^ 3 M), что должно быть лучше, когда D / d мало.

Даже если D / d больше, вы все равно можете быть в порядке, если сможете выработать стратегию отсечения. Например, если мы проверяем расстояние 5 точки сетки от нашего образца, и эта точка сетки уже помечена как расстояние 1 от предыдущего образца, то все точки сетки "за" этой точкой сетки проверять не нужно потому что предыдущий образец будет ближе к текущему, который мы обрабатываем. Все, что вам нужно сделать, - это (и я не думаю, что это легко, но должно быть выполнимо), определить, что означает «за пределами», и выяснить, как выполнять итерацию по сетке, чтобы не выполнять какую-либо работу для областей, «выходящих за пределы» таких точек сетки .

Answer 2

Вы можете построить структуру поиска ближайшего соседа (Википедия) на ваших точках выборки, а затем запросить ее для каждой из ваших точек сетки. Есть несколько алгоритмов, упомянутых на странице Википедии. Возможно, вам подойдут окт-деревья, kd-деревья или R-деревья.

Answer 3

Взгляните на октр . Это структура данных, часто используемая для эффективного разделения трехмерных пространств таким образом, чтобы повысить эффективность поиска объектов, которые находятся рядом друг с другом в пространстве.

Answer 4

записка о методе Кита Рэндалла, расширение ракушек или кубиков вокруг стартовых точек:
Можно расширять в различные заказы. Вот некоторый псевдокод в стиле Python:

S = set of 1m startpoints
near = grid 500x500x500 -> nearest s in S
    initially s for s in S, else 0
for r in 1 .. D:
    for s in S:
        nnew = 0 
        for p in shell of radius r around s:
            if near[p] == 0:
                near[p] = s
                nnew += 1
        if nnew == 0:
            remove s from S  # bonk, stop expanding from s

«Прекратить расширение с раннего» - хорошо в 1d (уклон слева, уклон справа); но 2d / 3d оболочки нерегулярны.
Проще / быстрее делать целые кубы за один проход:

near = grid 500x500x500 -> { dist, nearest s in S }
    initially { 0, s } for s in self, else { infinity, 0 }
for s in S:
    for p in approximatecube of radius D around s:
        if |p - s| < near[p].dist:  # is s nearer ?
            near[p] = { |p - s|, s }

Здесь «приблизительный куб» может быть полным кубом DxDxD, или вы можете обрезать углы, как (здесь 2d)

0 1 2 3 4 
1 1 2 3 4 
2 2 3 4 4
3 3 4 4
4 4 4

Тоже, с числами Эрика, в среднем 500 ^ 3 / 1M ~ 2 ^ 7 ~ 5 ^ 3 пустых за точку выборки. Итак, я сначала подумал, что 5x5x5 кубов вокруг 1M точек выборки будет охватывать большую часть всей сетки. Не так, ~ 1 / e точек сетки остаются пустыми - распределение Пуассона.

Answer 5

Один из подходов, который может подходить или не устраивать ваше приложение, состоит в том, чтобы изменить ваше мышление и определить каждую «точку» сетки как центр куба, который делит ваше пространство на ячейки. Затем у вас есть трехмерный массив таких ячеек и сохраните точки в ячейках - выберите наиболее подходящую структуру данных. Чтобы использовать ваши собственные слова, поместите точки в ведра на первое место.

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

РЕДАКТИРОВАТЬ: поискать в поисках частица-частица и частица-частица-сетка может дать вам некоторые идеи.