Всем привет!

Есть:
2Д(или 3Д) пространство, в котором присутствует некое кол-во объектов с координатами x,y(,z)

Суть задачи:
Каким образом осуществляется такая операция, как, нахождение объектов в радиусе R от точки P?

1)Простейшее решение - это, конечно, перебор всех объектов, проверка расстояния от них до P и выборка соответствующих критериям. Конечно же, такой подход очень неэффективен при большом количестве объектов в большом пространстве. Например, при поиске всех магазинов в радиусе 100 метров от дома №3 по улице Васина по базе данных, содержащей все магазины Москвы... 

2) Мне на ум приходит что то навроде графа [G1], в котором каждый объект имеет связи с несколькими ближайшими.
Имея некий начальный объект мы можем по принципу рекурсии проверять соседние объекты до тех пор, пока расстояние не превысит R.
Чтобы определить начальный объект при задании произвольной точки P можно ввести дополнительные "якоря" - опорные точки, имеющие определённый радиус и список объектов, находящихся от опорной точки не дальше значения радиуса. Для точки P будем находить соответствующий ей якорь, внутри него перебором выбирать ближайший к ней объект.
Чтобы оптимизировать алгоритм при большом размере пространства - можно якоря также хранить в виде иерархического графа [G2], по сути являющимся разметкой области на прямоугольные области, внутри которых также могут быть размечены прямоугольные области (а уже для области имеется список объектов внутри неё).

3) Или же взять последнюю строчку из варианта 2: разметка на квадраты, внутри которых также размечены квадраты (убрать G1, фигачить объекты сразу в G2). По идее этого достаточно для более-менее четкого определения подмножества объектов для поиска?


Правильно ли я мыслю?
Возможно, кто то подскажет примеры реализации (в общем виде описания алгоритмов и/или кодом), чтобы не изобретать велосипед совсем с нуля))

И сразу в продолжение... Задачу можно немного переформулировать так:
Каким образом осуществляется нахождение N ближайших объектов заданного типа к объекту O? Например, на нашей карте есть база данных не только по магазинам, но также и по 195 другим типам объектов, и нам нужно выбрать именно 10 ближайших магазинов...
Рациональнее ли будет держать индекс для каждого типа объектов? Особенно при случае, когда одному объекту может соответствовать несколько типов...
Или же стоит использовать подход варианта 2 и заранее предусматривать связи между объектами, исходя из поставленной задачи (координат, типов и т.п.)?

Это сообщение отредактировал(а) nucer - 4.11.2012, 08:09

деревья или сетки

деревья: https://en.wikipedia.org/wiki/Kd-tree

сетка - по сути то, что описано в #3 - просто делим пространство на NxMxK ячеек и записываем в кадой ячейке ссылки на объекты, которые полностью или частично в ней находятся, ну и при поиске просто перебираем нужные ячейки вместо всего пространства

деревья не заточены под конкретный радиус, но по ним нужно проходиться

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

Это сообщение отредактировал(а) maxim1000 - 4.11.2012, 13:22

мысль неплохая. таким графом является триангуляция Делоне или диаграмма Вороного (это двойственные графы)
трудоемкость построения такого графа - O(NlogN)

Добавлено через 3 минуты и 9 секунд
выбор метода, видимо, должен зависеть от того, как часто добавляются точки в множество и как часто осуществляется поиск. возможно, есть и другие факторы, влияющие на решение, например, если одни точки могут быть центром заведомо чаще, чем другие

maxim1000, спасибо! R-дерево как раз соответствует разбиению на прямоугольные области (G2). K-мерное дерево - если честно немного вынесло мне мозг, не понял, пока какому принципу там строятся плоскости (а именно, как определяется оптимальный угол наклона плоскости к осям)...

baldina, спасибо огромное, действительно ценная информация!) Как раз триангуляция Делоне это видимо то, что нужно в случае G2.
Сразу забегая вперёд (рабочий код, чтобы понять на 100% пока ещё не написал )) хочу спросить: как к получившемуся в результате триангуляции графу добавить всё те же "якоря", не соображу как это должно выглядеть... Есть мысль, что нужно строить ещё окружности (или может прямоугольные области?), но анализируя не точки, а по окружности, с помощью которых строился сам граф? И так можно аппроксимировать n раз, пока в идеале не сведем к одной окружности, охватывающей все точки?  На словах звучит логично, но вот реализация пока очень туманна...

В общем всем спасибо, пока буду разбираться, информации предостаточно 

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

Добавлено через 4 минуты и 18 секунд

это суть тоже разбиение на прямоугольные области. рассмотрите 2d дерево, его просто понять. если обычное дерево поиска сортирует точки по одному критерию (1d), то 2d дерево - по x и y, kd дерево - по k размерностям. k-я размерность соответствует k-му уровню в дереве.

просто перпендикулярно одной из осей

перпендикулярность в пространстве размерности больше 3х моск и выносит