LINUX.ORG.RU

Задача индексирования


0

0

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

Понятно, что на каждом шаге по времени можно пройтись по этому списку точек и определить соседей и провзаимодействовать их. Но это очень стремно O(n^2). На выручку приходит параллельная merge сортировка и все становится O(n*log(n)). Но я не достаточно счастлив со своими решениями. Первое принадлежит не мне и состоит в разбиении плоскости на клетки и ведении учета какая точка в какой клетке. Мое решение - три списка иметь по каждой координате и на каждом шаге по времени их сортировать. В итоге соседи будут соседями во всех трех списках.

Уверен, что-то есть стандартное или кто-то уже это делал. Предложите подход, пожалуйста.

★★★

Ответ на: комментарий от dmitry_vk

Много ссылок там битых. Но слайды распечатал и сейчас буду перед сном читать (у меня ночь начинается как раз). Похоже на то что ОЧЕНЬ надо! Спасибо огромное.

atoku ★★★ ()

> Уверен, что-то есть стандартное или кто-то уже это делал. Предложите подход, пожалуйста.

Разбиваешь плоскость на ячейки размером дельта, для поиска соседей смотришь ближайшие 9 ячеек, все, O(n). Гугли по spatial hashing.

slovazap ★★★★★ ()
Ответ на: комментарий от slovazap

Спасибо. Что-то вроде этого у нас и есть. Но я думал, что должно быть много теории на эту тему. Хотя бы на тему того, как выбирать размер ячеек, например. Кроме того, может есть что-то еще...

atoku ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.