Я пытаюсь найти структуру пространственного индекса, подходящую для конкретной задачи: используя структуру данных объединения-поиска, я хочу соединить \ связать точки, которые находятся в определенном диапазоне друг от друга.У меня много точек, и я пытаюсь оптимизировать существующее решение, используя лучший пространственный индекс.
Сейчас я использую простую двумерную сетку, индексирующую каждый квадрат ширины [пороговое расстояние]моя карта точек, и я ищу потенциальные объединения, ища точки в соседних квадратах в сетке.
Затем я вычисляю квадрат евклидова расстояния до комбинаций соседних ячеек, который я сравниваю с моим квадратным порогом, и яиспользуйте структуру union-find (оптимизированную с использованием сжатия пути и т. д.) для построения групп точек.
Вот несколько иллюстраций метода.Одиночные черные точки фактически представляют собой набор точек, принадлежащих ячейке сетки, а исходящие цветные стрелки представляют фактическое сравнение расстояний с внешними точками.
(Я также проверяю потенциальные связанные точки, которые принадлежат тем же ячейкам).
Используя этот шаблон, я убеждаюсь, что не буду дважды сравнивать расстояние, используя правильный шаблон "соседней ячейки", который не перекрывается с уже протестированным материалом при итерации по ячейкам сетки.
Проблема в том, что этот подход еще недостаточно близок к тому, чтобы быть достаточно быстрым, и я пытаюсь заменить метод «индекса пространственной сетки» чем-то, что может быть быстрее.
Я посмотрелв квадродерево в качестве подходящего пространственного индекса для этой задачи, но я не думаю, что он подходит для решения этой проблемы (я не вижу способа выполнить повторные проверки «соседей» для конкретной ячейки более эффективно с использованием квадродерева), новозможно я ошибаюсь в этом.
Поэтому я ищу лучший алгоритм \ структуру данных, чтобы эффективно индексировать мои точки и запрашивать их о близости.
Заранее спасибо.