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

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

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

Быстрый поиск ближайшего соседа

Страницы: 1 2 >
EvilDream © (2006-02-10 17:07:00)
Здравствуйте!

Возможно это не касается напрямую Delphi, но так как я пишу в основном на Delphi, то и пишу в эту ветку.

Есть такая задачка:

На прямоугольном поле, размером N*M, например 10000x10000, располагаются случайным образом достаточно большое количество точек K (предположим 100000).
Каждая точка имеет координаты Xi,Yi. В каждый момент времени точки перемещаются, то есть меняют свои координаты.
Задача -наиболее оптимальным образом для любой точки (Xk,Yk) в какой-либо момент найти ближайшую к ней точку.

Решение напрашивается:
Перебираем расстояния от точки (Xk,Yk) до всех остальных точек ( sqr(Xi-Xk)+sqr(Yi-Yk) ) и там, у кого оно окажется минимальным - тот и есть ближайший сосед.
Неоптимальность решения заключается в том, что нужно для большого числа точек (K-1) рассчитывать сумму квадратов.

Может, кто-нибудь предложит другую технологию поиска ближайшего соседа?
Математическую модель (модель представления данных) можно изменить, это не критично.
Использование СУБД для хранения координат точек и быстрого поиска по индексу недопустимо, так как, как я уже сказал, точки постоянно меняют свои координаты, а update в СУБД работает слишком медленно.

Cash (2006-02-16 11:45:00) [1]
Дубинка (13.02.06 23:04) [28]:
Товарищ, вы это к чему? Пример с потолка и совершенно не относится к
теме ветки! Сколько тебе извесно алгоритмов построения линии?, а
окружности?

NeyroSpace © (14.02.06 11:28) [30]:
Разбиение на сегменты приведет к трате перещетов относительно сегмента
каждой точки, и это не будет поднимать производительности.

Вот сижу и молчу :))), как умный. :Р
Итересно, а додумается еще кто нибудь до того, до чего я додумался? :)))
Если что, конечно, то я все объясню. (при том, что этот метод самый
быстрый из всех мной попробованных)
Но, из спортивного интереса... молчу!

NeyroSpace (2006-02-14 11:28:00) [2]
>Дубинка (13.02.06 23:04) [28]
Он имел ввиду другое.

>Cash © (13.02.06 16:55) [27]
Сегментация избавит от необходимости 2 раза возводить в кварат + изымать корень для каждой точки.
IMHO попадение в круг нужно анализировать только для отобранного множества точек, пападающего в некий квадрат dx, dy.
А если для точек прийдется вводить признак принадлежности к этой группе, то почему бы заодно не разбить все точки на n-е количество групп?
Тогда будет необходимо просматривать только главную группу в которую и попала точка и смежные группы, в которых могут находиться ближайщие точки.
Хотя можно сделать, чтобы группы перекрывались и т.д. :-)

Джо (2006-02-13 23:15:00) [3]
> [28] Дубинка (13.02.06 23:04)
> Блин скока тут умных постов.... половина мне кажется вообще
> странной....

Не мудрено, Дубинка.

Дубинка (2006-02-13 23:04:00) [4]
Блин скока тут умных постов.... половина мне кажется вообще странной....
Прочитал внимательно тока первые и последние....
Cash - на мой взгляд предложил полнейший бред (извините). Во первых, алгоритм рисования окружности....
Скомпильте этот код:
for i := 1 to 100 do
Ellipse(Form1.canvas.handle, 100 - i, 100 - i, 100 + i, 100 + i);
end;
и вы заметите, что некоторые точки будут пропущены. На более крутые алгоритмы будет затрачиваться огромное время, а смыслу не так уж и много.....

А то что мне пришело мне в голову - крайне просто :)
Создать Field: array[1..10000, 1..10000] of Boolean;
Если конечно не жалко нескольких метров памяти.... Но это пожалуй быстрейший способ.

Cash (2006-02-13 16:55:00) [5]
EvilDream © (11.02.06 21:57) [26]:
Совет:
- откажись от сегментации поля на области, мощности это не прибавит,
ведь считать то много придется.
- введи понятие области видимости, до каких пределов искать точку,
это съузит проблему алгоритма. (так же это повысит мощность алгоритма
поиска по окружностям, там областью видимости будет макс. радиус)
- сделай процедуру перемещения точки критической секцией, то есть
храня положения точки не только в точке, но и на поле, в виде указателя
на нее, представь процедуру перемещения точки абсолютно не делимой
операцией, и реалиуй ее примерно так:
Ставим клетку поля (указатель) на которой стоим в nil; Перемещаем себя; Ставим клетку поля (указатель) на которой на себя;

Это должно гарантировать некоторое быстродействие.

EvilDream (2006-02-11 21:57:00) [6]

> MBo © (10.02.06 18:18) [13]
> > Zeqfreed © (10.02.06 18:40) [17]

Этот метод даст ужасное быстродействие при уменьшении количества точек

Не дает покая идея с квадратами:

> Cash © (11.02.06 14:46) [25]

Реализацией ее я займусь чуть позже, а пока некоторые мысли вслух:
Положим К-количество точек, S -площадь поля, s-площадь квадрата
Видимо, существует экстремум быстродействия при определенном значении отношения (К*s/S).

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

Оптимальное соотношение, по-видимому, можно получить только экспериментально.

Cash (2006-02-11 14:46:00) [7]
EvilDream © (10.02.06 17:07):
Если у нас имеется матрица - поле, на которой распологается офигенно
много объектов (точек), причем положение объекта хранится и в объекте
и в соотвтствующей клетке матрицы-поля, то самый быстрый и надежный
способ поиска бизжайшего соседа будет способ основенный на рисовании
окружности. Потаму, как:
- окружность непрерывна
- минимальная толщина линии окружности равна одной клетке.
- окружность можно назвать идеальной 2D фигурой.

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

И как это теперь применить к поиску соседа?
Постепеноо увеличивая радиус от 1 к произвольному максимуму, который
меньше кратчайшего расстояния центра вращения до границы поля,
постепенно проходим все клетки поля и останавливаемся на первом же
вхождении объекта (точки) в линию окружности.
Проще говоря, рисуем ряд окружностей с центром в той точке, которая
ищет соседа, и смотрим первую попавшуюся точку на самой меньшей
из окружностей.

При этом метод всеравно слишком трудоемкий для постоянного запуска,
поэтому его либо оформляют в поток, либо вызывают разово по мере
необходимости.

Hint Lite (2006-02-11 13:22:00) [8]
Если координаты - целочисленные, то, учитывая ограниченность пространства, для ускорения вычисления квадратов целых чисел, можно при запуске приложения рассчитать таблицу квадратов - от 0 до 9999. Скорость определения квадрата целого числа в таком случае возрастает приблизительно в 3 раза (в зависимости от типа процессора).

TUser (2006-02-11 10:56:00) [9]
Я бы предложил такую структуру - деерво координат Х. Каждая координата ссылается на дерево кординат Y. Правда, памяти много надо, но ближайшая точка ищется обходом этих двух деревьев.

На практике помогал способ [13] - программируется просто, скорость удвлетворительная была, но задача стояла существенно меньшего размера.

EvilDream (2006-02-11 02:03:00) [10]
Спасибо всем, кто принял участие в обсуждении

> McSimm © (10.02.06 17:59) [8]

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

> MBo © (10.02.06 18:18) [13]
> Zeqfreed © (10.02.06 18:40) [17]

Идея с квадратами- супер, если удастся сделать накладные расходы (по перемещению из квадрата в квадрат) достаточно малыми - то, как мне кажется, это сработает.

Leonid Troyanovsky (2006-02-10 19:26:00) [11]

> EvS (10.02.06 18:03) [9]

> Вычисляются координаты, а потом проверяется есть ли точка
> с такими координатами.

Раз уж наступил weekend, позволю себе перед уходом одну сагу.
Один из моих давнишних одногрупников (работавший программистом
в Октагоне) защищал диплом по теме: "Оптимизация процесса наблюдения
за динамическими объектами" (попросту говоря, речь шла о подлодках).
Ну, и после обсуждения ряда моделей, включая Беллмана и Винера
со всем численным моделированием, вдруг прозвучал потрясший меня
вывод: оказывается, для того чтобы оптимально наблюдать за оными
динамическими объектами достаточно наблюдать оные в двух пунктах:
отправления и назначения, а каким образом достигнут последний -
совершенно неважно (вот, она - оптимизация).

Если до этого случая я не очень доверял военной науке, то после этого
я проникся, бо - глубоко.

--
Regards, LVT.

Leonid Troyanovsky (2006-02-10 18:56:00) [12]

> McSimm © (10.02.06 18:50) [19]

Это, как бы, все равно.
Бо, в соответствии с [1]: 10000*10000/100000 = 1000, т.е. ~30,
что и было отмечено в [16].

--
Regards, LVT.

McSimm (2006-02-10 18:50:00) [13]

> Если найти ближайшую, то более ничего и не требуется.

по X и по Y (а не расстояние)

в другом своем посте я расписал подробнее

MBo (2006-02-10 18:47:00) [14]
Если движутся не все точки постоянно - то можно предложить еще один метод - построить диаграмму Вороного (это из области триангуляции), и при движении точки модифицировать диаграмму - это будет выгоднее, чем каждый раз перестраивать ее с нуля.

Zeqfreed (2006-02-10 18:40:00) [15]
Как вариант развития мыслей изложенных MBo [13]: можно разбить поле на квадраты, для каждого квадрата хранить список точек, лежащих в нем. При выходе за границу квадрата, соотвественным образом модифицировать список. Таким образом, число точек, для которых необходимо вычислять расстояние по полной формуле заметно сократится, так же сразу можно будет пропускать квадраты в которых нет ни одной точки.

P.S. Перечитал [13], два раза, возможно имелось в виду то же самое, что я сейчас описал :)

Leonid Troyanovsky (2006-02-10 18:38:00) [16]

> McSimm © (10.02.06 17:29) [1]
> Если сначала найти ближайшие точки по X и по Y, то, как
> минимум, можно отсечь множество точек, лежащих вне этой
> прямоугольной области,

Если найти ближайшую, то более ничего и не требуется.

Попробуем рассуждать несколько иначе.
Скажем, на каком расстоянии может оказаться ближайший сосед
при данных условиях? У меня получилось порядка > 30.
Т.е., в среднем, перебор около 1000 "соседей". Сл-но, если в каждой
(значимой) точке сохранять направление (1/8) и плотность нахождения
соседей в каждом направлении можно предложить перспективные
направления поиска даже при условии, что координаты искомого могут
меняться( с учетом, того, что чем дальше соседи, тем меньше меняется
направление поиска).
Т.е. существует некая мера, позволяющая выделить наиболее
перспективное направление поиска. Также ясно, что при поиске все
пройденные узлы должны актуализировать информацию о положении
соседей в соответствии с результатами проведенных розыскных
мероприятий.

--
Regards, LVT.

McSimm (2006-02-10 18:32:00) [17]

> StriderMan © (10.02.06 18:19) [14]

:)
Только теперь я понял суть предложения искать точки на расстоянии 1,2,3...

Но даже если координаты исключительно целые числа - все равно такой способ не применим.
Как, например, определить какая из двух точек [7,4] и [5,3]
ближе к точке [0,0]

StriderMan (2006-02-10 18:19:00) [18]
Извиняюсь. Думал что координаты точек соответствуют из расположению в массиве.

Можно отсортировать массив по координатам (сначала Х, потом У), наверняка быстрее будет чем все квадраты считать.

А в каком виде вообще точки хранятся?

MBo (2006-02-10 18:18:00) [19]
В статике подобные задачи часто решаются с помощью построения quadtree - дерева. Возможно, есть подобные алгоритмы и для динамической системы. Навскидку из простого можно предложить, например, создать массив неких динамических структур размером, скажем, 100х100, и при перемещении точки из одного квадрата в другой перекидывать ее в соотв. структуру.

McSimm (2006-02-10 18:11:00) [20]
и главный вопрос (класс 4й кажется) - сколько точек может лежать на расстоянии N от заданной ?

Страницы: 1 2 >

Наверх

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