Алгоритм размещения сетки над неупорядоченным множеством точек

Question

Учитывая большой набор (от десятков тысяч до миллионов) неупорядоченных точек, представленных в виде трехмерных декартовых векторов, каков хороший алгоритм для создания правильной квадратной сетки (с заданным пользователем интервалом), которая охватывает все точки?Некоторые ограничения:

1. Сетка должна быть квадратной и правильной
2. Мне нужно иметь возможность регулировать интервал сетки (длину стороны одного из квадратов), в идеалес одной переменной
3. Я хочу сетку минимального размера, то есть каждый «блок» в сетке должен содержать хотя бы одну из неупорядоченных точек, и каждая неупорядоченная точка должна быть заключена в «блок»
4. Возвращаемым значением алгоритма должен быть список координат точек сетки

Для иллюстрации в 2D задан этот набор точек:

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

и для шага сетки X / 2 одним из возможных возвращаемых значений алгоритма будут координаты этих красных точек (пунктирные линии только для иллюстрации):

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

Python предпочтительнее длярешения, хотя псевдокод тоже хорош.

РЕДАКТИРОВАТЬ: Я думаю, что мое первое описание того, что мне было нужно, возможно, было немного нечетким, поэтому я добавил некоторые ограничения и изображения, чтобы прояснить ситуацию.

Answer 1

Я бы посоветовал вам сделать дерево kd .Это быстрый, простой и простой в реализации:

И код Википедии:

class Node: pass

def kdtree(point_list, depth=0):
    if not point_list:
        return

    # Select axis based on depth so that axis cycles through all valid values
    k = len(point_list[0]) # assumes all points have the same dimension
    axis = depth % k

    # Sort point list and choose median as pivot element
    point_list.sort(key=lambda point: point[axis])
    median = len(point_list) // 2 # choose median

    # Create node and construct subtrees
    node = Node()
    node.location = point_list[median]
    node.left_child = kdtree(point_list[:median], depth + 1)
    node.right_child = kdtree(point_list[median + 1:], depth + 1)
    return node

Вы бы немного его изменили, чтобы соответствовать вашим ограничениям.

Answer 2

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

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

Пройдите через данные еще раз, чтобы выделить каждую точку ячейке в сетке, используя сетку с точкой минимума каждой координаты и указанным интервалом (например, X_cell = Math.floor ((x_i - x_min) / интервал)). Используйте словарь или массив для записи количества точек в каждой ячейке.

Теперь распечатайте координаты ячеек, в которых есть хотя бы одна точка.

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

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

Конечно, у вас есть три аспекта для беспокойства. Вы можете работать с ними по одному, пока не получите сокращение числа ячеек. Это локальный минимум, но не может быть глобальным минимумом. Один из способов поиска других локальных минимумов - начать заново со случайно выбранной начальной точки.

Answer 3

Как насчет Диаграмма Вороного ?Он может быть сгенерирован в O(n log n) с использованием алгоритма Fortunes .

Я не знаю, решает ли это вашу проблему, но диаграммы Вороного очень «естественны».Они очень распространены в природе.

Пример (из Википедии):

Answer 4

У меня есть опыт кластеризации сетки в 2D и я реализовал пример в коде C #. http://kunuk.wordpress.com/2011/09/15/clustering-grid-cluster/

Это может обработать шаговую ручку шагов 1, 2 и 4. Вам придется изменить код и обновить его до 3D-пространства. Надеюсь, что это дает вам некоторые идеи.

Код выполняется в O (m * n), где m - количество сеток, а n - количество точек.

Answer 5

Найдите квадрат минимальной площади, который охватывает все точки.Неоднократно подразделить каждый квадрат на 4 субквадрата (таким образом, переходя от 1 до 4 до 16 до 64 до ...).Остановитесь прямо перед тем, как один из квадратов станет пустым.Нетрудно доказать, что результирующая сетка является не более чем в четыре раза более грубой, чем оптимальное решение (ключевая идея: гарантируется, что пустой квадрат содержит хотя бы один квадрат из любой сетки, как минимум, вдвое больше).* Вероятно, эту константу можно уменьшить, введя случайный перевод.

Answer 6

Если вы хотите, чтобы ячейки сетки были квадратными и регулярными, вам, скорее всего, понадобится Octree .Если вы можете ослабить квадрат и регулярное ограничение, вы можете создать kd-tree .