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

← →
EvilDream © (2006-02-10 17:07) [0]

Здравствуйте!

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

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

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

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

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

← →
McSimm © (2006-02-10 17:29) [1]

Если сначала найти ближайшие точки по X и по Y, то, как минимум, можно отсечь множество точек, лежащих вне этой прямоугольной области, т.к. они однозначно дальше найденных. Оставшиеся перебирать по сумме квадратов.

← →
Джо © (2006-02-10 17:35) [2]

Поддерживаю идею [1] McSimm ©. Сам именно так и поступал. То есть, сначала смотрим по обоим осям +- определенную величину, отсеивая все, что не входит в этот диапазон. Затем уже определяем расстояния и выбираем наименьшнее. Как сделать еще быстрее — не представляю.

← →
Джо © (2006-02-10 17:39) [3]

Конечно, изменив "модель представления данных", можно коренным образом ускорить алгоритм, сведя его к тривиальному. Например, если хранить точки не в прямоугольной, а в полярной системе координат :)

← →
EvS (2006-02-10 17:44) [4]

Проверяй наличие точек на расстоянии 1,2,3... от (Xk,Yk) первая и будет ближайшей.

← →
Джо © (2006-02-10 17:47) [5]

> [4] EvS (10.02.06 17:44)
> Проверяй наличие точек на расстоянии 1,2,3... от (Xk,Yk)
> первая и будет ближайшей.

Для того, чтобы узнать, что точка находится "на расстоянии 1,2,3" от нашей, нужно вычислить расстояние до всех точек, не се па? ;)

← →
Leonid Troyanovsky © (2006-02-10 17:48) [6]

> Джо © (10.02.06 17:39) [3]

> если хранить точки не в прямоугольной, а в полярной системе
> координат :)

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

--
Regards, LVT.

← →
Джо © (2006-02-10 17:55) [7]

> [6] Leonid Troyanovsky © (10.02.06 17:48)

Да нет, я в шутку предложил. :^)

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

← →
McSimm © (2006-02-10 17:59) [8]

перечитал свой пост, показалось не очень понятно непонятно.

чуть подробнее:
для каждой Xi,Yi вычисляем dX,dY - расстояния до базовой точки по осям
из полученных значений выбираем большее по модулю и используем эту точку для поиска соответствующей границы прямоугольной области:
если dX > dY - точка используется для поиска границы по X
если dX < dY - точка используется для поиска границы по Y

в обоих группах находим наименьшее dX или dY (по обе стороны от базовой точки)

полученная прямоугольная область содержит в себе искомую ближайшую
проверка всех Xi,Yi на принадлежность прямоугольной области выполняется легко
для оставшихся точек вычисляется квадрат расстояния

← →
EvS (2006-02-10 18:03) [9]

Джо © (10.02.06 17:47)[5]

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

← →
StriderMan © (2006-02-10 18:08) [10]

> EvS (10.02.06 17:44) [4]
> Проверяй наличие точек на расстоянии 1,2,3... от (Xk,Yk)
> первая и будет ближайшей.

Поддерживаю
самый быстрый способ
перебирать ВСЕ - это кошюнство!

← →
McSimm © (2006-02-10 18:09) [11]

> EvS (10.02.06 18:03) [9]
> StriderMan © (10.02.06 18:08) [10]

Вы или просто шутники, или не достаточно компетентны, в любом случае просьба -- лучше не писать не очень умные советы.

1. А какие координаты у точки лежащей на расстоянии 1 от заданной точки, например [5.121, -7.322)?
2. Точки лежащие на расстоянии 0.99 не ищем ?
3. 0.998 ?

← →
McSimm © (2006-02-10 18:11) [12]

и главный вопрос (класс 4й кажется) - сколько точек может лежать на расстоянии N от заданной ?

← →
MBo © (2006-02-10 18:18) [13]

В статике подобные задачи часто решаются с помощью построения quadtree - дерева. Возможно, есть подобные алгоритмы и для динамической системы. Навскидку из простого можно предложить, например, создать массив неких динамических структур размером, скажем, 100х100, и при перемещении точки из одного квадрата в другой перекидывать ее в соотв. структуру.

← →
StriderMan © (2006-02-10 18:19) [14]

Извиняюсь. Думал что координаты точек соответствуют из расположению в массиве.

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

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

← →
McSimm © (2006-02-10 18:32) [15]

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

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

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

← →
Leonid Troyanovsky © (2006-02-10 18:38) [16]

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

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

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

--
Regards, LVT.

← →
Zeqfreed © (2006-02-10 18:40) [17]

Как вариант развития мыслей изложенных MBo [13]: можно разбить поле на квадраты, для каждого квадрата хранить список точек, лежащих в нем. При выходе за границу квадрата, соотвественным образом модифицировать список. Таким образом, число точек, для которых необходимо вычислять расстояние по полной формуле заметно сократится, так же сразу можно будет пропускать квадраты в которых нет ни одной точки.

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

← →
MBo © (2006-02-10 18:47) [18]

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

← →
McSimm © (2006-02-10 18:50) [19]

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

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

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

← →
Leonid Troyanovsky © (2006-02-10 18:56) [20]

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

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

--
Regards, LVT.

← →
Leonid Troyanovsky © (2006-02-10 19:26) [21]

> EvS (10.02.06 18:03) [9]

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

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

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

--
Regards, LVT.

← →
EvilDream © (2006-02-11 02:03) [22]

Спасибо всем, кто принял участие в обсуждении

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

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

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

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

Я бы предложил такую структуру - деерво координат Х. Каждая координата ссылается на дерево кординат Y. Правда, памяти много надо, но ближайшая точка ищется обходом этих двух деревьев.

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

← →
Hint Lite (2006-02-11 13:22) [24]

Если координаты - целочисленные, то, учитывая ограниченность пространства, для ускорения вычисления квадратов целых чисел, можно при запуске приложения рассчитать таблицу квадратов - от 0 до 9999. Скорость определения квадрата целого числа в таком случае возрастает приблизительно в 3 раза (в зависимости от типа процессора).

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

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

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

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

> 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).

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

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

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

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

← →
Дубинка (2006-02-13 23:04) [28]

Блин скока тут умных постов.... половина мне кажется вообще странной....
Прочитал внимательно тока первые и последние....
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;
Если конечно не жалко нескольких метров памяти.... Но это пожалуй быстрейший способ.

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

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

>Дубинка (13.02.06 23:04) [28]
Он имел ввиду другое.

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

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

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

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

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