Мастера 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 в СУБД работает слишком медленно.

McSimm (2006-02-10 18:09:00) [21]

> 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 ?

StriderMan (2006-02-10 18:08:00) [22]

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

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

EvS (2006-02-10 18:03:00) [23]
Джо © (10.02.06 17:47)[5]

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

McSimm (2006-02-10 17:59:00) [24]
перечитал свой пост, показалось не очень понятно непонятно.

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

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

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

Джо (2006-02-10 17:55:00) [25]
> [6] Leonid Troyanovsky © (10.02.06 17:48)

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

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

Leonid Troyanovsky (2006-02-10 17:48:00) [26]

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

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

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

--
Regards, LVT.

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

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

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

Джо (2006-02-10 17:39:00) [29]
Конечно, изменив "модель представления данных", можно коренным образом ускорить алгоритм, сведя его к тривиальному. Например, если хранить точки не в прямоугольной, а в полярной системе координат :)

Джо (2006-02-10 17:35:00) [30]
Поддерживаю идею [1] McSimm ©. Сам именно так и поступал. То есть, сначала смотрим по обоим осям +- определенную величину, отсеивая все, что не входит в этот диапазон. Затем уже определяем расстояния и выбираем наименьшнее. Как сделать еще быстрее — не представляю.

McSimm (2006-02-10 17:29:00) [31]
Если сначала найти ближайшие точки по X и по Y, то, как минимум, можно отсечь множество точек, лежащих вне этой прямоугольной области, т.к. они однозначно дальше найденных. Оставшиеся перебирать по сумме квадратов.

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

Наверх

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