Re: Поиск ближайшей точки | |
---|---|
Crispy Сообщений: 18571 Дата регистрации: 16.05.2005 |
Хотя тут похоже тоже можно найти выигрыш!
Что если перевести все координаты из x,y в полярные координаты? В смысле как раз в это самое расстояние (а лучше в квадрат расстояния, проще для вычилений) и в угол - т.е. собственно в R2 и A. Правда при этом получаем уже два дополнительных, заранее вычисляемых поля. Но зато тогда поиск мне кажется будет получаться попроще, чем поиск в квадрате. Например сначала по индексу ищем группу точек с ближайшем расстоянием от 0, куда попадает наша исходная. Т.е. как бы получается сегмент. А затем отсекаем в нем конкретно ближайшие - через ближайший по значению угол из другого индекса. Разница при отсечении сегмента в том, что он конечен даже на бесконечной плоскости. В отличие от полосы, получаемой при линейном отсечении например по X, чтобы затем отсекать квадрат по Y. Можно наверно попробовать модифицировать то самое оптимальное решение Игоря к полярным координатам. ------------------ В действительности все иначе, чем на самом деле. (Антуан де Сент-Экзюпери) Исправлено 2 раз(а). Последнее : Crispy, 26.03.10 11:51 |
Re: Поиск ближайшей точки | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Нет никакого выигрыша при переводе в полярные координаты (вычисление "расстояния до нуля" это всего-лишь половина работы по переводу в полярные координаты) - я уже писал про это. В любом случае формула расстояния между 2-мя точками БУДЕТ включать координаты второй точки "внутри" формулы - и потому нельзя сделать какой-то хитрое преобразование, чтобы координаты одной точки были с одной стороны оператора сравнения, а коордианты второй - с другой. Т.е. привести к тому, чтобы можно было заменить поиск на вычисление некоторой "константы" основанной на координатах одной точки, и потом сравнивать её с постоянными значениями вычисленными на основе координат другой точки массива (а только такое значение можно рассчитать заранее - очевидно что нельзя заранее рассчитать значение зависящее от координат точки поиска - т.к. эти координаты неизвестны).
------------------ WBR, Igor |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
forum.foxclub.ru Функция paul() Думаю, поиск точки с помощью этого алгоритма можно ускорить, рассчитывая расстояние не до центра координат, а до центра облака точек. Но всё равно площадь просматриваемого кольца будет больше площади квадрата, что при равномерном распределнии точек даст тормоза. ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
Mitchman Сообщений: 9978 Откуда: Николаев Дата регистрации: 24.05.2002 |
Двухмерный объект не может быть описан менее 2 параметров - так же как 3 х мерный менее 3 х - и система координат не важна потому в любом случае - для двумерного объекта вы будете иметь две координаты и перевод из одной системы в другую только усложняет процесс ------------------ - «свидомые украинцы озабочены не столько созданием украинской культуры, сколько уничтожением русской» - Олесь Бузина |
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 |
Re: Поиск ближайшей точки | |
---|---|
Гулин Федор Сообщений: 4640 Откуда: Минск Дата регистрации: 24.10.2002 |
оффтоп
случайно сюда заглянул во у людей память я по образованюи математик - кстати учился очень неплохо читаю - и вижу что мой моск отказывается думать а у нас даже спец.курс - вычисл. геометрия как правильно заметил Leonid а по раобте мне таких задач не попадалось - все больше дебет с кредитом а без этого все это забывается конечно ну я думаю раз обсуждение заглохло - то проблема или решена или отпала онтоп |
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). Далее по принципу дерева:
Время усреднялось по 10,100,1000 поискам. Сейчас читаю [A name="http://ru.wikipedia.org/wiki/R-дерево"]R-Дерево на Wiki[/A] Надо попробовать. |
Re: Поиск ближайшей точки | |
---|---|
ssa Сообщений: 13008 Откуда: Москва Дата регистрации: 23.03.2005 |
А индексы правильные? ------------------ Лень - это неосознанная мудрость. Исправлено 1 раз(а). Последнее : ssa, 04.07.11 13:17 |
Re: Поиск ближайшей точки | |
---|---|
Goodwin Автор Сообщений: 3539 Откуда: Омск Дата регистрации: 03.05.2006 |
Не понял. Поиск в одном секторе? И сколько занимает перестроение дерева при добавлении точки? ------------------ Что мы знаем о лисе? Ничего. И то не все. (С)Б. Заходер |
Re: Поиск ближайшей точки | |
---|---|
Black_Cat Сообщений: 7 Дата регистрации: 02.12.2010 |
1. Гмм.. Недопонял насчет "правильности". Как писал индексы по id,x,y; при добавлении полей добавляются индексы по этим полям sectorx,sectory.
Делать индексы по нескольким полям не стал. Можно покумекать, но не получится ли слишком сложная прога?.. 2. Да, поиск ближайшей точки в одном секторе. Сорри, забыл добавить, что еще и в пределах небольшого квадратика от заданной точки. Вот так:
3. Добавление одной точки будет не шибко долгим. Не замерял. Но уточню: по формулировке задачи этого не требуется, или требуется чрезвычайно редко. |
Re: Поиск ближайшей точки | |
---|---|
ssa Сообщений: 13008 Откуда: Москва Дата регистрации: 23.03.2005 |
Не каждый индекс ускоряет работу. Фокс их использует? Выражения индексов можно увидеть? ------------------ Лень - это неосознанная мудрость. |
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 ЗЫ: Написал руками индексы. Ну лень мне вспоминать функцию выгрузки структуры. |
Re: Поиск ближайшей точки | |
---|---|
ssa Сообщений: 13008 Откуда: Москва Дата регистрации: 23.03.2005 |
И Ваше ИМХО совпадает с фоксовым? Почитайте про sys(3054) ------------------ Лень - это неосознанная мудрость. |
Re: Поиск ближайшей точки | |
---|---|
Black_Cat Сообщений: 7 Дата регистрации: 02.12.2010 |
Почесал репу еще разок.
Да, рашмор в данной ситуации однозначно скажет использует ли индексы. Т.о. по идее не будет. Соптимизировать можно было бы, если построить индекс сразу по расстоянию до данной точки. Т.е. выражение индекса:
x,y - координаты точки в таблице. Но это долго... Каждый раз при поиске придется строить индекс. Грустно однако. |
Re: Поиск ближайшей точки | |
---|---|
ssa Сообщений: 13008 Откуда: Москва Дата регистрации: 23.03.2005 |
Скрипт генерации тестовых данных увидим? Или будем все чисто теоритически рассуждать?
------------------ Лень - это неосознанная мудрость. |
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 |
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 |
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 |
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 |
Re: Поиск ближайшей точки | |
---|---|
leonid Сообщений: 3204 Откуда: Рига Дата регистрации: 03.02.2006 |
Простите, а не могли бы Вы привести формулы, по которым Вы вычисляете расстояние до границы сектора? |
© 2000-2024 Fox Club  |