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

Сообщений: 18571
Дата регистрации: 16.05.2005
Хотя тут похоже тоже можно найти выигрыш!
Что если перевести все координаты из x,y в полярные координаты?
В смысле как раз в это самое расстояние (а лучше в квадрат расстояния, проще для вычилений) и в угол - т.е. собственно в R2 и A.
Правда при этом получаем уже два дополнительных, заранее вычисляемых поля.

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

Разница при отсечении сегмента в том, что он конечен даже на бесконечной плоскости. В отличие от полосы, получаемой при линейном отсечении например по X, чтобы затем отсекать квадрат по Y.

Можно наверно попробовать модифицировать то самое оптимальное решение Игоря к полярным координатам.


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)




Исправлено 2 раз(а). Последнее : Crispy, 26.03.10 11:51
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Нет никакого выигрыша при переводе в полярные координаты (вычисление "расстояния до нуля" это всего-лишь половина работы по переводу в полярные координаты) - я уже писал про это. В любом случае формула расстояния между 2-мя точками БУДЕТ включать координаты второй точки "внутри" формулы - и потому нельзя сделать какой-то хитрое преобразование, чтобы координаты одной точки были с одной стороны оператора сравнения, а коордианты второй - с другой. Т.е. привести к тому, чтобы можно было заменить поиск на вычисление некоторой "константы" основанной на координатах одной точки, и потом сравнивать её с постоянными значениями вычисленными на основе координат другой точки массива (а только такое значение можно рассчитать заранее - очевидно что нельзя заранее рассчитать значение зависящее от координат точки поиска - т.к. эти координаты неизвестны).


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Crispy
Пересмотрел внимательно несколько раз, но так и не нашел.
forum.foxclub.ru
Функция paul()

Думаю, поиск точки с помощью этого алгоритма можно ускорить,
рассчитывая расстояние не до центра координат, а до центра облака точек.
Но всё равно площадь просматриваемого кольца будет больше площади квадрата,
что при равномерном распределнии точек даст тормоза.


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

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
Crispy
Хотя тут похоже тоже можно найти выигрыш!
Что если перевести все координаты из x,y в полярные координаты?....

Двухмерный объект не может быть описан менее 2 параметров - так же как 3 х мерный менее 3 х - и система координат не важна

потому в любом случае - для двумерного объекта вы будете иметь две координаты и перевод из одной системы в другую только усложняет процесс


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Mitchman

Сообщений: 9978
Откуда: Николаев
Дата регистрации: 24.05.2002
в качестве решения самой задачи должно выкиныть заведомо неподходящие

как вариант такого можно сперва выбрать например точку с наименьшим |X1-X0| и запомнить его |Y1-Y0| и дальше в расчете использовать только те что имеют |Y0-Y1| не больше запомненного а остальные можно сразу откинуть - и при больших объемах и большой плотности точек - может получиться большой выигрыш

если брaть саму математику - то я исхожу из принципа - что если я ищу LIM(0) От выражения ((X1-X0)^2+(Y1-Y0)^2) - то это раскладавется на сумму лимитов квадратов


------------------
-
«свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской»
-
Олесь Бузина




Исправлено 3 раз(а). Последнее : Mitchman, 26.03.10 15:15
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Гулин Федор

Сообщений: 4640
Откуда: Минск
Дата регистрации: 24.10.2002
оффтоп
случайно сюда заглянул
во у людей память
я по образованюи математик - кстати учился очень неплохо
читаю - и вижу что мой моск отказывается думать
а у нас даже спец.курс - вычисл. геометрия
как правильно заметил Leonid
а по раобте мне таких задач не попадалось - все больше дебет с кредитом
а без этого все это забывается конечно
ну я думаю раз обсуждение заглохло - то проблема или решена или отпала
онтоп
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Black_Cat

Сообщений: 7
Дата регистрации: 02.12.2010
Нашел эту тему когда сам думал о подобной проблеме.
делался поиск в одном миллионе точек. Индексы по id,x,y.
Результат 1: Тупой перебор - грустно. (специально проверил) Время порядка 30с.
Результат 2: Тупой select - та же картина.
Время усреднялось по 2-3 поискам.

Изменение в таблице:
Добавлены поля sectorx и sectory - деление по 10 единиц. sectorx=floor(x/10). Естественно есть индексы.
Результат 3: Делается select в пределах секторов. Находим минимальное расстояние. Если до какой-то стенки сектора ближе чем до найденной точки, то расширяем поиск и на соседний сектор. Уже прям весело! Время поиска порядка - 0.2с.
Время усреднялось по 10 и 100 поискам.

Изменение в таблице (по сравнению с исходной!):
Добавлены поля: bxby - id следующей точки с большим x и большим y; bxsy - id следующей точки с большим x и меньшим y; sxsy - id следующей точки с меньшим x и меньшим y; sxby - id следующей точки с меньшим x и большим y.
Добавление точек:
Сделал по умолчанию первую точку (0,0).
Далее по принципу дерева:
DO WHILE nextid>0
SEEK nextid
IF newx=>x THEN
IF newy=>y THEN
nextid=bxby
IF EMPTY(nextid) THEN
REPLACE bxby WITH i
ENDIF
ELSE
nextid=bxsy
IF EMPTY(nextid) THEN
REPLACE bxsy WITH i
ENDIF
ENDIF
ELSE
IF newy=>y THEN
nextid=sxby
IF EMPTY(nextid) THEN
REPLACE sxby WITH i
ENDIF
ELSE
nextid=sxsy
IF EMPTY(nextid) THEN
REPLACE sxsy WITH i
ENDIF
ENDIF
ENDIF
ENDDO
Результат 4: Поиск аналогично по дереву. Супер! Время менее 1 тысячной секунды! Минус: Добавление миллиона точек произошло за 21 минуту!
Время усреднялось по 10,100,1000 поискам.

Сейчас читаю [A name="http://ru.wikipedia.org/wiki/R-дерево"]R-Дерево на Wiki[/A]
Надо попробовать.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ssa

Сообщений: 13008
Откуда: Москва
Дата регистрации: 23.03.2005
Black_Cat
Индексы по id,x,y.
...
Результат 2: Тупой select - та же картина.
...
Естественно есть индексы.
А индексы правильные?

------------------
Лень - это неосознанная мудрость.




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

Сообщений: 3539
Откуда: Омск
Дата регистрации: 03.05.2006
Black_Cat
Делается select в пределах секторов.
Не понял. Поиск в одном секторе?

И сколько занимает перестроение дерева при добавлении точки?


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

Сообщений: 7
Дата регистрации: 02.12.2010
1. Гмм.. Недопонял насчет "правильности". Как писал индексы по id,x,y; при добавлении полей добавляются индексы по этим полям sectorx,sectory.
Делать индексы по нескольким полям не стал. Можно покумекать, но не получится ли слишком сложная прога?..

2. Да, поиск ближайшей точки в одном секторе.
Сорри, забыл добавить, что еще и в пределах небольшого квадратика от заданной точки.
Вот так:
выбираем сектор по x и по y
SELECT * ;
FROM points ;
WHERE (sectorx=fromxsector) AND (sectory=fromysector) ;
INTO CURSOR fromsector READWRITE
IF EMPTY(i_square) THEN
i_square=1
ENDIF
выбираем квадратик вокруг заданной точки, так, чтобы в него попало от 0 до 100 точек
done=.f.
DO WHILE not done
SELECT * ;
FROM fromsector ;
WHERE (fromx-i_square<=x) AND (x<=fromx+i_square) ;
AND (fromy-i_square<=y) AND (y<=fromy+i_square) ;
INTO CURSOR selpoint
selpcnt=RECCOUNT('selpoint')
DO CASE
CASE selpcnt=0
i_square=i_square*1.9
CASE selpcnt>100
i_square=i_square/2.1
otherwise
done=.t.
ENDCASE
ENDDO
считаем расстояния до выбранных точек
find_dist=distance(i_square,i_square)
find_id=0
SELECT selpoint
SCAN
i_dist=distance(fromx,fromy,x,y)
IF find_dist>i_dist THEN
find_dist=i_dist
find_id=id
ENDIF
SELECT selpoint
ENDSCAN

3. Добавление одной точки будет не шибко долгим. Не замерял. Но уточню: по формулировке задачи этого не требуется, или требуется чрезвычайно редко.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ssa

Сообщений: 13008
Откуда: Москва
Дата регистрации: 23.03.2005
Black_Cat
1. Гмм.. Недопонял насчет "правильности". Как писал индексы по id,x,y; при добавлении полей добавляются индексы по этим полям sectorx,sectory.
Делать индексы по нескольким полям не стал. Можно покумекать, но не получится ли слишком сложная прога?..
Не каждый индекс ускоряет работу. Фокс их использует? Выражения индексов можно увидеть?

------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Black_Cat

Сообщений: 7
Дата регистрации: 02.12.2010
Согласен, но влет не пришли в голову какие-нить осмысленные, а потом не стал думать, т.к. занялся "деревянным" методом.
Ну насчет использует ли... ИМХО, должен.
Выражения - просто поля.
Назв Тип Выражение
ID Regular id
X Regular x
Y Regular y
SECTORX Regular sectorx
SECTORY Regular sectory
BXBY Regular bxby
BXSY Regular bxsy
SXBY Regular sxby
SXSY Regular sxsy

ЗЫ: Написал руками индексы. Ну лень мне вспоминать функцию выгрузки структуры.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ssa

Сообщений: 13008
Откуда: Москва
Дата регистрации: 23.03.2005
Black_Cat
ИМХО, должен.
И Ваше ИМХО совпадает с фоксовым?
Почитайте про sys(3054)


------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Black_Cat

Сообщений: 7
Дата регистрации: 02.12.2010
Почесал репу еще разок.
Да, рашмор в данной ситуации однозначно скажет использует ли индексы.
Т.о. по идее не будет.
Соптимизировать можно было бы, если построить индекс сразу по расстоянию до данной точки. Т.е. выражение индекса:
ACOS(SIN(fromy)*SIN(y)+COS(fromy)*COS(y)*COS(x-fromx))
где, fromx,fromy - координаты данной точки;
x,y - координаты точки в таблице.
Но это долго... Каждый раз при поиске придется строить индекс. Грустно однако.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
ssa

Сообщений: 13008
Откуда: Москва
Дата регистрации: 23.03.2005
Скрипт генерации тестовых данных увидим? Или будем все чисто теоритически рассуждать?


------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
IMHO бессмысленно делать такие поля - никакой разницы для фокса не будет, если это искусственное поле заменить на простое выражение (x between m.fromx-10 AND m.fromx-10) AND (y between m.fromy-10 AND m.fromy+10) которое вполне успешно использует уже имеющиеся индексы по полям x и y. Более того, мне кажется что могут возникнуть ошибки, если точка "from" будет находится близко к границе "ячейки" - тогда в расчёт попадут "дальние" точки из этой же ячейки, но НЕ попадут точки из соседних ячеек находящиеся возможно ближе... Впрочем алгоритм в любом случае не доведен до ума - ибо в варианте когда ПЕРВЫЙ запрос возвращает 0 записей (в искомой ячейке нет точек), нужно вообще-то не из пустого курсора (сколоько ты не "расширяй" область поиска, а он пустым и останется), а из всей таблицы запрос делать...
Вообще-то это всё подробнейшим образом обмусолено в районе 3-й страницы...


------------------
WBR, Igor




Исправлено 1 раз(а). Последнее : Igor Korolyov, 04.07.11 19:06
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Black_Cat

Сообщений: 7
Дата регистрации: 02.12.2010
Так. Похоже надо собрать в кучку.
Уточню сначала - большая часть работы проделана до нахождения и прочтения этой ветки. Поэтому прошел через все те же грабли.
Далее:
Мои исходные данные:
Диапазон -180<=x<=180, -90<=y<=90 с точностью 7 знаков. Это координаты на матушке Земле.
Сначала все делалось на просто рандомном заполнении всей области. Сейчас сделал процедурку с областями, заполненными плотнее. Хотя переделаю еще.
Пропробовал сам все алгоритмы полученные и участниками этой ветки.
Алгоритм с предварительным ограничением квадратика (кажется Игорем предложен) самый выгодный. Как и было выяснено выше.
НО! При очень больших массивах данных порядка 10^7-10^8 уже тоже становится тяжеловато.
Поэтому было сделано дополнение: все точки распределены по заранее выбранным квадратам.
Выборка по этим квадратам отрабатывает быстрее. А в худшем случае исходный алгоритм прорабатывает 4 таких квадрата.
А потом попробовал "деревянный" вариант, т.е. с построеним дерева.
В окончательном варианте прога будет на си писаться под Linux,Android итд. А пробовать мне проще в фоксе.
Мусор чуть поубираю выложу исходник для просмотра чтоб не на пальцах. Может даже сегодня.



Исправлено 1 раз(а). Последнее : Black_Cat, 05.07.11 14:14
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
1 - Из 5 страниц обсуждения не вынесен ГЛАВНЫЙ вывод - "квадратные" методы поиска это ФОКСОВАЯ особенность - точнее использование особенностей работы его оптимизатора - каким макаром ты собираешься использовать особенности фоксовой оптимизации при разработке на "си под Linux,Android итд." - для меня большая загадка...
2 - Приведенный тобой код некорректен. Во-первых он тупо зациклится если в начальном квадрате вообще не будет точек (из "ничего" нельзя получить "что-то" как бы ты не расширял условия отбора). Во-вторых ДАЖЕ если в начальном квадрате БУДЕТ точка, это далеко не факт что она будет оптимальной, и что можно спокойно отбрасывать все соседние квадраты. Рассмотрим простейшую ситуацию:
даны 2 точки с координатами (1,1) и (10,10) - по твоим метрикам они попадут соответственно в "сектора" (0,0) и (1,1). Теперь найдём "ближайшего" соседа к точке (9,9) - по твоему алгоритма, т.к. эта точка находится в секторе 0,0 то нужно брать только точки этого сектора - в итоге мы начинаем работать с точкой 1,1 и т.к. она одна, очень быстро приходим к выводу что она "ближайшая" - банальная логика, да и простой расчёт показывают что это вовсе не так - расстояние до неё примерно 11.31, а до "сразу отброшенной" точки (10,10) всего 1.41 Fail!
3 - Если речь идёт про геокоординаты, то вся твоя система моментально летит к чертям, поскольку расстояния между точками на ШАРЕ, да ещё если речь идёт о широте и долготе, рассчитываются вовсе не по таким же формулам как на плоскости


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
Black_Cat

Сообщений: 7
Дата регистрации: 02.12.2010
Могу вынести и вывод и еще что-нибудь...
1. Реляционные БД, насколько я знаю, не имеют сколько-нибудь принципиальных отличий. Если в фоксе можно построить индексы по x и по y, и нельзя построить индекс типа расстояние_до_точки(X1,Y1), если мы не знаем заранее координаты X1 и Y1. То и в MySQL то же самое, и в SQLite, и в..... можно не продолжать? А от языка (C,Fox,Basic,Pascal...) зависит только и исключительно какие функции как называются, ну разве что где-нибудь есть функция, а где-нибудь нет. От операционной системы (Win,Lin,Androin,WinMo...) зависит интерфейс и то, как хранятся файлы на носителях. Достаточно расписал? Я неплохо представляю все выше указанные отличия. И, на мой взгляд, проверять многие вещи можно и на фоксе, т.к. в нем проще работать с БД.
2. Приведенный код работает на ура. Хотя замечание об отсутствии точек в секторе правильно, но просто не рассматривалась подобная возможность (надо учесть!). По выбору расстояния уже писалось, что проверяется расстояние до границы сектора, и если оно меньше расстояния до точки в секторе, то происходит расширение на соседний сектор. Найдена будет точка (10,10).
3. Расстояние в моем случае рассчитывается по формуле: ACOS(SIN(y1)*SIN(y2)+COS(y1)*COS(y2)*COS(x2-x1))/PI()*180 в экваториальных градусах. Где x - долгота, y - широта. Т.е. единица приблизительно равна 111,11 км.

ЗЫ: Не думайте, пожалуйста, что все вокруг соображают и знают меньше Вас.
ЗЗЫ: Давайте будем более конструктивны. Если Вы можете сказать, в чем конкретно окажется существенная разница при использовании C и SQLite (например), и таким образом некорректна проба на VFP9, то лучше напишите именно это. А если не знаете, то лучше не говорить того чего не знаешь.
ЗЗЗЫ: Еще раз повторюсь проблема цикленья при отсутствии точек в секторе конструктивна. Пересмотрю алгоритм.



Исправлено 1 раз(а). Последнее : Black_Cat, 06.07.11 13:21
Ratings: 0 negative/0 positive
Re: Поиск ближайшей точки
leonid

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Black_Cat
проверяется расстояние до границы сектора
Простите, а не могли бы Вы привести формулы, по которым Вы вычисляете расстояние до границы сектора?
Ratings: 0 negative/0 positive


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

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

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