Подскажите алгоритмы быстрого геометрического поиска?

← →
Unknown user © (2007-07-16 12:55) [0]

Имеется набор точек с двумерными координатами, как быстро отыскать ближайшую к произвольной Pnt точку, не перебирая весь набор? Как быстро найти ближайшую к Pnt точку в заданном направлении Dir, и углом поиска Ang?

Предполагаю, что следует использовать деревья. Что посоветуете?

← →
Elen © (2007-07-16 12:57) [1]

> не перебирая весь набор?

Что мешает перебрать?

← →
ЮЮ © (2007-07-16 13:00) [2]

> Что мешает перебрать?

Очевидно, количество, и время рассчета.
А человек "глянул на бумажку" - и сразу нужную точку видит :)

← →
Unknown user © (2007-07-16 13:00) [3]

требования к быстродействию

← →
MBo © (2007-07-16 13:41) [4]

>как быстро отыскать ближайшую к произвольной Pnt точку, не перебирая весь набор

QuadTree

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

← →
StriderMan © (2007-07-16 13:44) [5]

а как точки хранятся?
если массивом координат? - тогда или упорядочивать или все перебирать

если массивом типа array[x,y] of boolean то все намного быстрее можно сделать

← →
Sapersky (2007-07-16 14:00) [6]

Здесь:
http://www.blackpawn.com/texts/cellular/default.html
(раздел "Making It Fast")
описывается вариант с bsp-деревьями, мне, правда, так и не удалось его реализовать.

← →
MBo © (2007-07-16 14:38) [7]

Если задача такая:
Дан набор точек P[], и для произвольной точки X, не входящей в набор, нужно найти ближайшую из набора P, то быстрее всего будет построить диаграмму Вороного (объект, связанный с триангуляцие Делоне), и тогда поиск можно будет делать за O(Log(N)) или даже за O(1) (при раскраске диаграммы в уникальные цвета)

← →
Unknown user © (2007-07-16 14:47) [8]

to StriderMan

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

to Sapersky

спасибо за ссылку, но вроде есть готовые реализации BSP.

to МВо

спасибо

← →
TUser © (2007-07-17 06:16) [9]

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

to TUser

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

to МВо

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

to Sapersky

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

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

to MBo

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

← →
Sapersky (2007-07-20 10:06) [13]

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

Там не совсем bsp, а, как выразился автор, "2D bastard son of a sphere-tree and a bsp-tree". Дело в том, что стандартные деревья, что bsp, что quad, дают "линейное" разделение пространства, а здесь требуется "округлое", пардон за дилетантскую терминологию.
При реализации этого bastard son кол-во сравнений у меня получилось сопоставимое с линейным поиском (возможно, что-то не так понял).

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

Подскажите алгоритмы быстрого геометрического поиска? Найти похожие ветки