Всем привет. У меня есть неупорядоченный массив точек(в моем случае

в трёхмерном пространстве). Есть критерий связанности точек: если евклидово расстояние между ними меньше заданного. Как можно за быстро найти группу связанных точек? У меня быстрее чем O(n^2) не получается.

Возможно если строить kd-дерево за O(nlogn) то можно что то выиграть?

Что подразумевается под "группой связанных точек"? Найти какую-то компоненту связности нужного размера или разбить все точки на компоненты связности (или вообще что-то ещё)?

что внутри группы от любой точки до любой другой есть путь по цепочке связанных точек

Ну пустую группу бери

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

да, я пытался сделать такое окно. ускорение и правда было. С 25 секунд до 12. В два раза конечно, но мне бы секунды в 2 уложиться

хм... а что если от стартовой точки отсортировать не по координате, а по сферам с радиусами d, 2d, 3d, 4d, ... ? Потом начинаем от стартовой: тогда соседи точек, заключенных между сферами 1 и 2 могут быть только среди точек, заключенных между 2 и 3. И дальше итеративно. Ну хоть не всех со всеми проверять придётся. А когда первый кластер выделю - повторная разбивка на сферы от новой точки из ещё не занятых

Да, это кластеры. DBSCAN подходит, кажется.

Тут проблема, что уже в двумерном пространстве не сделаешь индекс “по сферам”, без приседаний. Это будет какой-то нетривиальный алгоритм similarity search.

У меня есть ещё концепции, но пока я не знаю как бы их реализовать по удобному. 1) а может есть способ запихать всё в трёхмерный массив, но как то сэкономить на пустых элементах? потому что он сильно разряжен. В массиве то обход вширину легко делать. Визуально то эти кластеры легко выделяются глазами. Потому что мы не анализируем пустоту, а только сами точки 2) а может как то брать случайную точку и забыстро проверять подходит ли она к уже имеющимся кластерам?(да, во множественном числе). И если она общая для двух кластеров - объединять их. если не общая нидлякого - будет началом нового кластера 3) а как бы это дело распараллелить? количество ядер то может быть большим. а есть ещё и видеокарты

Разреженная трехмерная сетка работает с помощью хэштаблицы. В трехмерном пространстве это можно сделать, если точки довольно равномерно расположены, но этот алгоритм сломается, если в каких-то зонах высокая концентрация точек, тогда получится тот же N^2 Координаты точки округляем по размеру, на который нам нужно отступать, условно - единица. Строим хэштаблицу динамических массивов, и все точки по своим округленным координатам распихиваем в эти массивы. Теперь идем по всем ключам хэштаблицы, находим 26 смежных ключей, и для каждой пары центральная - перефирийная округленная точка добавляем грани смежности в граф. Ну потом уже ищем по графу связанные подграфы.

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

пример точек:

Можно совместить этот приём с приёмом "разделяй и влавствуй": 1) бьём облако плоскостью по одной из координат на левое и право (предположим по медиане) 2) запускаемся рекурсивно на левом 3) запускаемся рекурсивно на правом 4) по результатам обоих запусков строим облако, которое находится на расстоянии от плоскости разбиения <= d из левого и правого (уже отсортированное по одной из координат) 5) применяем приём из реплая - опционально, на самом деле, на "плоское" облаком можно ещё раз применять итерацию нашего алгоритма, но уже по другой координате чтобы получить "линейное" облако, на линейное облаком уже можно с кайфом применять алгоритм из реплая от очень большой плотности точек это всё равно не спасёт, но кажется, что в такой ситуации не спасёт ничего

Вот тут вопрос: допустим я храню графы как матрицы смежности. А почему вообще надо хранить как граф? А не просто точки в массиве

Матрица смежности крайне неэффективна, это N^2

Я предложил строить граф, чтобы потом, после того, как найдены грани, можно было обойти графовым алгоритмом грани, чтобы найти связные подграфы.

Вопрос: а что если я буду хранить кластер как три avl-дерева? По х,y,z. И с номером точки, дополнительно. После этого я беру новую точку. Можно ли тогда за быстро проверить принадлежит она кластеру или нет? Спуститься по дереву по каждой из координат. Я найду ближайшую точку по х, по y и по z. Проверю только их на расстояние до добавляемой точки. Если хоть одна из них рядом - вставляю новую точку в деревья. Если все далеко - то новая точка начало нового кластера. Будет ли работать такая "быстрая" проверка на вхождение в кластер? Ну и если точка принадлежит двум кластерам - надо их как то объединять за быстро, но это уже другая история

Разве это будет работать для набора точек: (0, 0), (1, 5), (5, 1), (2, 2), где стартовая точка (0, 0)?

Ну тогда ещё надо определиться с расстоянием связности и с тем какую точку добавляем. Или (0,0) - и есть стартовый кластер из одной точки?

Не могу понять что значит связные подграфы. Подграф ещё понятно - кусок текущего графа. А связный это как?

Ща. Кажется сообразил. Я не все точки загоняю в разреженную сетку, а потом чето анализирую в ней. Я начинаю строить графы и для каждого из графов храню свою собственную разреженную сетку. Тогда при добавлении новой точки я могу за быстро проверять: входит точка в окрестность одного из имеющихся графов или нет. Ну и объединять графы если новая точка принадлежит сразу двум как то за быстро наверное тоже смогу Так?

Окей, тогда похоже, что вот это будет работать за что-то типа O(n*k).

Я имею в виду, что после первой стадии алгоритма, который я предлагаю, вы получите просто граф, где есть компоненты. https://en.wikipedia.org/wiki/Component_(graph_theory)

Нет, единый граф строится. В нем образуются компоненты. Это части графа, между которыми нет транзитивных связей. https://en.wikipedia.org/wiki/Component_(graph_theory)

возможно я то то не так понял. вот я строю граф в котором связаны все 80_000 точек. получаю 80_000^2 связей. потом все их обхожу BFS? я явно что то не так понял.. Или граф строится из кубиков, которые являются элементами хэш-таблицы?

Связей будет не n^2, а столько, сколько их есть.

В этом графе будут ребра только для тех точек, которые ближе.

Нет, я предлагал искать ребра по смежным кубикам. А сами ребра - это те точки, которые точно ближе даметра.

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

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

Сделать это просто. Берем хэштаблицу, ключ - целочисленные координаты, значение - вершины графа, котопые попали в кубик. Потом идем по всем ключам этой таблицы просто, и генерируем окрестность из 26 ключей, которые надо проверить.