:: Игры Разума
Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Задача:
Есть таблица с координатами точек (PoindId i, coordX i, coordY i)
Нужно найти в этой таблице точку, ближайшую к заданным координатам.
Т.е. что-то вроде
lnPointX=300
lnPointY=200
lnMinDistance=-1
lnMinPointId=0
scan
lnDistance=sqrt((lnPointX-coordX)^2+(lnPointY-coordY)^2)
if lnMinDistance=-1 or lnDistance<lnMinDistance
lnMinDistance=lnDistance
lnMinPointId=PointId
endif
endscan

Проблема: слишком медленно.

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

Или поиск на сях переписать.
Или и то и другое.

Видел кто подходящие алгоритмы - ничего толкового придумать не могу.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
А если запросом?
CREATE CURSOR points (PoindId i, coordX i, coordY i)
FOR i=1 TO 20
INSERT INTO points VALUES (i, INT(500*RAND()),INT(500*RAND()))
ENDFOR
lnPointX=300
lnPointY=200
SELECT TOP 1 *, sqrt((lnPointX-coordX)^2+(lnPointY-coordY)^2) as distance ;
FROM points;
ORDER BY distance
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Не, запрос примерно в два раза дольше скана выполняется.
Тут, как мне кажется, нужно изначальную таблицу как-то оптимизировать для быстрого поиска.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Вот чего в голову пришло:
index on bintoc(coordx)+bintoc(coordy) tag xy
set Near On
seek bintoc(nPointX)
seek bintoc(coordx)+bintoc(nPointY)
lnDistance=d()
seek bintoc(nPointX-lnDistance)
scan rest while coordX<=nPointX+lnDistance for lnDistance>d()
lnDistance=d()
lnMinPointId=pointId
endscan
function d
return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)
индексирует долго, за то потом ищет разов в сто быстрее скана.

Думаю дальше.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер




Исправлено 1 раз(а). Последнее : Goodwin, 01.03.10 17:27
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
Извлечение квадратного корня - лишняя операция на стадии определения минимума.

Функция квадратного корня гладкая и возрастающая. Это значит, что если значение функции минимальное, то минимально и значение аргумента этой функции.

Если взять формулу определения расстояния без корня, то имеем

(lnPointX-coordX)^2+(lnPointY-coordY)^2

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

(lnPointX^2 + lnPointY^2) - 2*(lnPointX*coordX + lnPointY*coordY) + (coordX^2 + coordY^2)

В этом переупорядочивании 3 группы:

(lnPointX^2 + lnPointY^2) - константа, которую можно вычислить до начала расчета
(coordX^2 + coordY^2) - значение, никак не зависящее от положения точки, расстояние до которой определяем. Т.е. это значение можно добавить отдельным столбцом в таблицу координат

Ну, и третье слагаемое, которое, собственно, и придется рассчитывать

CREATE CURSOR points (PoindId i, coordX i, coordY i, square i)
FOR i=1 TO 20
INSERT INTO points (PoindId, coordX, coordY) VALUES (i, INT(500*RAND()),INT(500*RAND()))
ENDFOR
replace all square with (coordX^2 + coordY^2)
lnPointX = 300
lnPointY = 200
lnSquare = lnPointX^2 + lnPointY^2
SELECT TOP 1 *, m.lnSquare + square - 2*(coordX*m.lnPointX + coordY*m.lnPointY) as SquareDist ;
FROM points ;
order by 2

Правда, тут я не уверен, насколько предварительное вычисление части выражения ускорит/замедлит поиск по сравнению с запросом без предварительных вычислений

SELECT TOP 1 *, ((m.lnPointX - coordX)^2 + (m.lnPointY - coordY)^2) as SquareDist ;
FROM points ;
order by 2

Это можно проверить только экспериментально
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
Упрощаем логику дальше

Функция квадрата - это парабола. Если "разрезать" по вертикальной оси, то опять же имеем гладкую возрастающую функцию. Т.е. минимум функции совпадает с минимумом аргумента.

Убираем квадрат. Прямая линия тоже гладкая возрастающая. Но в контексте данной задачи для поиска минимума подходит только положительная часть. Отрицательную часть надо брать по модулю.

В общем, вместо суммы квадратов можно использовать суммы по модулю

SELECT TOP 1 *, (abs(m.lnPointX - coordX) + abs(m.lnPointY - coordY)) as ModuleDist ;
FROM points ;
order by 2

Что будет быстрее - опять же проверяется экспериментально.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Не знаю, как это повлияет на скорость, но можно попробовать сначала отсечь ненужные области сравнения, а потом вычислять расстояния по оставшимся точкам.
select * from points ;
where between(coordX,lnPointX-lnMaxX,lnPointX+lnMaxX) ;
and between(coordY,lnPointY-lnMaxY,lnPointY+lnMaxY) ;
into cursor Temp
SELECT TOP 1 *, (abs(m.lnPointX - coordX) + abs(m.lnPointY - coordY)) as ModuleDist ;
FROM Temp ;
order by 2
где lnMaxX, lnMaxY - максимальные расстояния по X и Y между двумя соседними точками в таблице, т.е. в данном случае постоянные величины, вычисленные заранее.



Исправлено 1 раз(а). Последнее : ry, 01.03.10 12:41
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Попробовал оптимизировать через добавление поля и избавление от корня по варианту Владимира.
Время поиска не изменилось.
Т.е. тормоза не от вычислений, а от перебора записей.

Стало быть помогут только индексы и отсечение записей без просмотра оных.

Попробую индексами разбить всё поле на клетки,
и рассматривать их по разворачивающейся спирали...


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Владимир Максимов
В общем, вместо суммы квадратов можно использовать суммы по модулю
Нет, так не получится. Точка (0.6, 0.6) ближе к началу координат, чем (1, 0), а сумма модулей у нее больше.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14614
Дата регистрации: 01.04.2004
Если ф-ия имеет несколько экстремумов, то нахождение min-значения возможно только перебором всего массива, другие численные методы не подойдут.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
leonid
Владимир Максимов
В общем, вместо суммы квадратов можно использовать суммы по модулю
Нет, так не получится. Точка (0.6, 0.6) ближе к началу координат, чем (1, 0), а сумма модулей у нее больше.
Точно. А я все думаю, что-то меня смущает в этом переходе от квадратов к числам, но проверять не стал. Для целочисленных коордитат тоже не подходит: (3,3) ближе к (0,0), чем (5,0), хотя сумма модулей будет больше в первом случае. Но уже выяснилось, что проблема не в вычислениях. Интересно, а сколько записей в таблице и как она проиндексирована?
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
leonid
Владимир Максимов
В общем, вместо суммы квадратов можно использовать суммы по модулю
Нет, так не получится. Точка (0.6, 0.6) ближе к началу координат, чем (1, 0), а сумма модулей у нее больше.

Да, забыл про переход через 1. Если известно, что расстояние по любой координате всегда больше 1, то замена квадратов на модуль - подойдет. Если нет, то не получится
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14614
Дата регистрации: 01.04.2004
Кстати, надо вычислить для каждой точки длину вектора относительно точки начала координат, затем вычислить длину ветора для исходной точки и искать сравнивая длины векторов.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
Goodwin
Вот чего в голову пришло:
index on bintoc(coordx)+bintoc(coordy) tag xy
set Near On
seek bintoc(nPointX)
seek bintoc(coordx)+bintoc(nPointY)
lnDistance=d()
seek bintoc(nPointX-lnDistance)
scan rest while coordX<=nPointX-lnDistance for lnDistance>d()
lnDistance=d()
lnMinPointId=pointId
endscan
function d
return sqrt((nPointX-coordX)^2+(nPointY-coordY)^2)
индексирует долго, за то потом ищет разов в сто быстрее скана.

Думаю дальше.

Как мне кажется, данный код в принципе не корректен.



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

Или есть какие-то еще ограничения?
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
PaulWist

Сообщений: 14614
Дата регистрации: 01.04.2004
Типа этого:

CREATE CURSOR test (x int, y int, r n(12,2) DEFAULT SQRT(x**2 + y**2))
INSERT INTO test (x, y) VALUES (1 , 1)
INSERT INTO test (x, y) VALUES (1 , 2)
INSERT INTO test (x, y) VALUES (2 , 1)
INSERT INTO test (x, y) VALUES (2 , 2)
INSERT INTO test (x, y) VALUES (3 , 3)
m.x = 3.5 && точка которую ищем
m.y = 1 && точка которую ищем
m.r = SQRT(m.x**2 + m.y**2) && длина вектора для искомой точки
SELECT TOP 1 a.r, x, y FROM (select ABS(m.r - r) as r, x, y FROM test ) a ORDER BY a.r

Только нет уверенности, что будет "летать" (тот же самый scan), вообще надо задаваться доверительным интервалом, тогда будет значительно быстрее


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
PaulWist
вообще надо задаваться доверительным интервалом, тогда будет значительно быстрее
Я выше приводил код, просто отсекающий в плоскости координат прямоугольник с центром в искомой точке, в котором гарантированно будет как минимум одна (а если повезет, то только одна) точка из таблицы. Дальше поиск по этой области, по идее, должен быть быстрым. Хотя будет ли быстрым само такое отсечение, можно проверить только на практике.



Исправлено 2 раз(а). Последнее : ry, 01.03.10 17:48
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Ересь все это, никакая оптимизация здесь невозможна. Дабы убедиться проведите мысленный эксперимент. Пусть эту же задачу вам предстоит решать, пользуясь только калькулятором, а исходная таблица перед вами на бумаге. Ежу понятно, что для каждой новой точки решить задачу можно только последовательно перебрав все строки в таблице. И любые дополнительные телодвижения, как то вычисление индексов, каких то предварительных рез-тов и пр.,
только замедлят процесс. Потому что все эти доп. телодвижения сводятся к одному и тому же - чтению всех записей из таблицы.
ЗЫ. Шальная мысль. Что, если для каждой точки исходной таблицы определить геометрическое место точек, расстояние от которых до этой точке не больше расстояния до любой другой точки этой таблицы? Тогда при переборе не надо вычислять сумму квадратов, достаточно проверить лежит ли наша точка в том самом "геометрическом месте".Тут одно плохо, я даже не представляю себе как это геометрическое место будет выглядеть Возможно, проверка на принадлежность точки этому месту будет гораздо дольше чем посчитать 2 квадрата.
Хотя в любом случае, как уже было сказано, время вычислений здесь пренебрежимо мало по сравнению со временем перебора записей.

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



Исправлено 1 раз(а). Последнее : medstrax, 01.03.10 19:10
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
medstrax
Ересь все это, никакая оптимизация здесь невозможна. (...) Потому что все эти доп. телодвижения сводятся к одному и тому же - чтению всех записей из таблицы.

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

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

medstrax
ЗЫ. Шальная мысль. Что, если для каждой точки исходной таблицы определить геометрическое место точек, расстояние от которых до этой точке не больше расстояния до любой другой точки этой таблицы?

Собственно, почти это и предложил ry. Только он вычислял расстояния до соседних (ближайших) точек. Но проблема данного решения в том, что оно не работает, если искомая точка окажется вне диапазона исходных точек.

Ну, например, возьмем для простоты одномерную систему (линию). Есть всего две точки с координатами 1 и 2. Расстояние между ними 1. Если искомая точка будет лежать в координатах от 0 до 3, то предварительное ограничение прекрасно работает. А если искомая точка будет иметь координату, скажем 5? Предварительная отсечка диапазона не оставит нам вообще ни одной точки!
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Владимир Максимов

Сообщений: 14097
Откуда: Москва
Дата регистрации: 02.09.2000
В порядке "бреда сумасшедшего"

Сама координатная сетка бесконечна? Т.е. координаты могут быть +/- бесконечность? Шаг сетки также никак не ограничен?

Это я к тому, нельзя ли заранее рассчитать минимальное расстояние для любой возможной точки координатной сетки? Загоняем результаты расчета в таблицу и дальше просто ищем по индексу заданную точку и считываем заранее рассчитанный результа.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Владимир Максимов
При использовании индексов чтение всех записей не происходит. Другой вопрос, можно ли здесь как-то "прикрутить" индекс. Хотя бы с целью предварительного ограничения области поиска.
Дык в том и суть - чтобы построить индексы для надо сперва прочитать все записи. Где здесь выигрыш? А строить индекс надо каждый раз заново для новых входных данных.
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 3 (Гостей: 3)

© 2000-2024 Fox Club 
Яндекс.Метрика