Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Unknown user © (2007-07-16 12:55:00)
Имеется набор точек с двумерными координатами, как быстро отыскать ближайшую к произвольной Pnt точку, не перебирая весь набор? Как быстро найти ближайшую к Pnt точку в заданном направлении Dir, и углом поиска Ang?

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

Sapersky (2007-07-20 10:06:00) [1]

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

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

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

Unknown user (2007-07-19 12:21:00) [2]
to MBo

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

MBo (2007-07-19 11:11:00) [3]
>Unknown user
Строится диаграмма Вороного, рисуется на битмапе, и каждая ее ячейка закрашивается уникальным цветом(например, цвет = номер точки набора). Тогда для каждой входящей точки просто проверяем цвет в ее координатах.
Если размерность пространства велика, и битмап такой не сделать, то разделить диаграмму горизонтальными линиями, проходящими через ее вершины, ребра диаграммы вместе с этими линиями образуют треугольники и трапеции, бинарный поиск полосы, потом бинарный поиск треугольника или трапеции

Unknown user (2007-07-19 10:47:00) [4]
to TUser

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

to МВо

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

to Sapersky

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

TUser (2007-07-17 06:16:00) [5]
Делишь пространство на квадратики, для каждого квадратика составляешь список точек. Это занимает время, но если сабжевое вычисление надо проводить много раз, то окупается.

Unknown user (2007-07-16 14:47:00) [6]
to StriderMan

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

to Sapersky

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

to МВо

спасибо

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

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

StriderMan (2007-07-16 13:44:00) [9]
а как точки хранятся?
если массивом координат? - тогда или упорядочивать или все перебирать

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

MBo (2007-07-16 13:41:00) [10]
>как быстро отыскать ближайшую к произвольной Pnt точку, не перебирая весь набор

QuadTree

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

ЮЮ (2007-07-16 13:00:00) [11]
> Что мешает перебрать?

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

Unknown user (2007-07-16 13:00:00) [12]
требования к быстродействию

Elen (2007-07-16 12:57:00) [13]

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

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

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »