| 0
- 22.05.2015 - 18:11
|
В общем, у многих наверняка есть архив своих (и не очень) GPS треков. У меня вот скопилось около трех сотен штук того добра. При планировании очередного похода возникает надобность найти все треки которые затрагивают интересующий регион. Кто и как решает эту проблему? Очевидные варианты, как разложить по папочкам - можно не указывать 8), т.к. больше интересют технические средства наподобие:      | | ||||||||||||||||||
| 121
- 26.05.2015 - 14:18
|
Вот более характерный пример - http://caucasia.ru/site/toponim/670 Смотри, это карточка вершины Псеашхо Южный и перечислены все имеющиеся у меня треки, которые проходят РЯДОМ с ней. НИ ОДИН из них не затрагивает вершину - никто из авторов этих треков не поднимался на эту вершину. Но это именно те треки, которые полезны при планировании маршрутов на Псеашхо Южный. Они отобраны по критерию "треки, проходящие на каком-то расстоянии от нужной точки" (я глянул, на Кавказии это не 1 км, а 2% градуса широты для простоты/скорости формулы). Где я не прав? | | ||||||||||||||||||
| 122
- 26.05.2015 - 14:21
|
Доп. к 121 - И это все работает автоматически (то есть реализовано "техническими средствами", как у автора). Мне не нужно вручную ничего переименовывать по каким-то там квадратам. Чем плох мой алгоритм, что ты так яро отстаиваешь альтернативные идеи, да еще и начинаешь докапываться к интерпретациям условия задачи? | | ||||||||||||||||||
| 123
- 26.05.2015 - 15:32
|
Паша, сначала ты спорили непонятно о чем со Светланой, теперь сам с собой. Выдыхай ) З.Ы. Алгоритм твой верен. Я даже сомневаюсь, что можно придумать что-то концептуально новое. | | ||||||||||||||||||
| 124
- 26.05.2015 - 15:57
| Цитата:
Цитата:
Не сложно и самому слепить показуху Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Не сложно и самому слепить показуху Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
Цитата:
| | ||||||||||||||||||
| 125
- 26.05.2015 - 16:05
| Цитата:
| | ||||||||||||||||||
| 126
- 26.05.2015 - 16:19
| Так это, проекция в прямоугольные координаты (xyz) только ради фильтрации дороговато, потому режут в базе по градусам а потом уточняют, или надо хранить еще и EPSG:3857 координаты | | ||||||||||||||||||
| 127
- 26.05.2015 - 16:29
| 126-wayerr >Если это мне, то 1% ближе к километру, чем 2%. Простая арифметика... | | ||||||||||||||||||
| 128
- 26.05.2015 - 16:34
| на широте питера это уже не так | | ||||||||||||||||||
| 129
- 26.05.2015 - 16:38
| Цитата:
| | ||||||||||||||||||
| 130
- 26.05.2015 - 16:45
| http://caucasia.ru/site/track/439 Почему бы и нет? | | ||||||||||||||||||
| 131
- 26.05.2015 - 16:51
| 130-wayerr >я в шоке.... сдаюсь! [а нет ли надежного трека на Колыму?] | | ||||||||||||||||||
| 132
- 26.05.2015 - 17:05
| Цитата:
| | ||||||||||||||||||
| 133
- 26.05.2015 - 17:06
| Цитата:
| | ||||||||||||||||||
| 134
- 26.05.2015 - 17:16
| Цитата:
А по поводу расчета ты что-то путаешь. Один градус широты почти одинаковый на всем земном шаре, в отличие от градуса долготы. Что, правда, дает еще большую оценку километража (больше 2 км), но если ты думаешь, что это зря, то ошибаешься. Если этот радиус сильно уменьшить (например до 100 метров), то куча полезных треков пройдет "мимо" нужной цели. Пока в результате поиска вываливается штук 5-10 рядом проходящих треков - это нормально. Я бы даже сделал алгоритм посложнее - которые выбирает такой радиус (каждый раз разный), чтобы в результатах было не менее скольки-то треков. Но это медленнее, поэтому см. выше. | | ||||||||||||||||||
| 135
- 26.05.2015 - 17:22
|
Разумеется (здесь терминология разнится) под "градусом широты" я имею ввиду расстояние равное расстоянию между параллелью N и N+1 градусов, которая почти одинаковая независимо от N, а не градус отмеренный "по параллели", что во многих источниках нелогично названо "градусом широты". Логично ведь что так как градус - единица измерения, то он должен измерять именно то, чего он градус. Если это градус широты, то это единица измерения широты. И именно такие отрезки (дуги) отделяют одну широту от другой. (это я для тех, кто сейчас тут попытается сумничать) | | ||||||||||||||||||
| 136
- 26.05.2015 - 17:26
|
Простой показательный пример-"запоминалочка" для тех кто сомневается как правильно сказать: 46 градусов северной широты - 45 градусов северной широты = 1 градус широты | | ||||||||||||||||||
| 137
- 26.05.2015 - 17:27
|
>Я бы даже сделал алгоритм посложнее - которые выбирает такой радиус (каждый раз разный), чтобы в результатах было не менее скольки-то треков. Но это медленнее, поэтому см. выше. можно выбирать top 10 треков отсортированных по возрастанию расстояния - это почти таже скорость | | ||||||||||||||||||
| 138
- 26.05.2015 - 17:29
| 137 - Кстати да, как вариант. Но это можно делать только в тех районах, где, наоборот - уже накопилось хотя бы 10 треков. А то по Карелии будут 10 треков: 1. Петрозаводск 2. Лагонаки 3. Лагонаки 4. Лагонаки .... | | ||||||||||||||||||
| 139
- 26.05.2015 - 17:31
| Кстати, там же на Кавказии "Ближайшие объекты" так и выводятся. | | ||||||||||||||||||
| 140
- 26.05.2015 - 17:33
| Для треков это, кстати, сделать нельзя. Нет такой простой формулы "расстояние от точки до трека", которую можно было бы засунуть в SQL и которая выводила бы одно число, по которому можно было сортировать таблицу результатов. | | ||||||||||||||||||
| 141
- 26.05.2015 - 17:35
| Опять же для скорости у меня из базы сначала выбираются "кандидаты", то есть треки, описанный прямоугольник которых содержить целевую точку. А уже они анализируются поточечно (ищется есть ли в таком треке точка, которая не более чем на "2% градуса" дальше цели). Одним запросом это сделать невозможно (еще и потому, что в базе данных не хранятся все точки трека, они хранятся в файле - в базе только координаты описанного прямоугольника). | | ||||||||||||||||||
| 142
- 26.05.2015 - 17:38
| Я ведь, как программист веб-проекта, должен еще сразу думать о будущем масштабировании. Чтобы ничего не переделывать, надо сразу подумать, как твой алгоритм будет работать, когда число сущностей (треков, в данном случае) достигнет, например миллиона. Сайт должен продолжать работать. Поэтому более живучи в таких случаях грубые алгоритмы, которые не точно математически, а иными хитрыми уловками обрабатывают данные, получая их за малое время. | | ||||||||||||||||||
| 143
- 26.05.2015 - 17:38
| Либо грубо получив выборку меньшого числа данных обрабатывают уже точнее, но только их (а не весь миллион). | | ||||||||||||||||||
| 144
- 26.05.2015 - 17:42
| Цитата:
| | ||||||||||||||||||
| 145
- 26.05.2015 - 17:50
|
Извините, я вас обманул. Скрипты на Кавказии писались хрен-знает-сколько лет назад. Вот сейчас изучил внимательнее тот скрипт, который выбирает "треки рядом" какой-то точки. На самом деле происходит следующее: Этап 1. Сначала из базы выбираются все треки "кандидаты", описанные прямоугольники которых с точностью 2% градуса широты содержат целевую точку. (Это SQL) Этап 2. Просматриваются все точки треков-кандидатов (на самом деле не более 500 равномерно выдранных из трека - опять же для ускорения) на предмет поиска существования точки, отстоящей не далее чем на 1 км от целевой. И они вот и выводятся в результат. (Это без SQL). 2% градуса - это я не там подсмотрел, пардон, все верно - радиус 1 км. Почему во втором этапе не используется база? Чтобы не хранить все точки в базе. Для нескольких треков кандидатов прочитать файл с треком и вызвать по 500 раз формулу вычисления расстояния в метрах для сервера несложно. Думаю, без ущерба можно уменьшить число проверяемых точек до 100. Редко встречаются пешие треки из 100 точек по 1 км между ними. | | ||||||||||||||||||
| 146
- 26.05.2015 - 18:12
| Цитата:
| | ||||||||||||||||||
| 147
- 26.05.2015 - 18:18
| +146 вынужден себя опровергнуть... не везет мне сегодня. Дома все видится иначе, чем на работе. Без косинуса - это просто 60 морских миль. Т.е. в твоем случае (2%) - это 0,02*60*1852=2222м. Но никак не километр :) | | ||||||||||||||||||
| 148
- 26.05.2015 - 18:20
| 147 - Никак не километр. Перечитай п. 145. | | ||||||||||||||||||
| 149
- 26.05.2015 - 18:21
|
147 - Я сначала написал в п. 121, что "(я глянул, на Кавказии это не 1 км, а 2% градуса широты для простоты/скорости формулы)." Так что я не говорил, что 2% это 1 км, я наоборот, сказал, что это "не 1 км". С чем ты споришь, не пойму? | | ||||||||||||||||||
| 150
- 26.05.2015 - 18:22
| 147 - Сначала определись, с чем именно ты споришь, а потом спорь :) | | ||||||||||||||||||
| 151
- 26.05.2015 - 18:23
| Потом, правда, выяснилось, что треки ищутся все же в 1 км, они выбираются с погрешностью 2% градуса, но это ведь не относится к нашу спору относительно того, что 1 км = 2% градуса широты. Когда найдешь, где я такое писал - покажи, самому интересно. | | ||||||||||||||||||
| 152
- 26.05.2015 - 18:25
| А 2% градуса широты выбраны не случайно - это как раз более чем в два раза больше радиуса, в котором ищется трек. Чтобы трек попал в результаты поиска даже, если целевая точка оказывается не включена в описанный прямоугольник трека, а находится за его пределами (если трек заканчивается, не доходя до точки). | | ||||||||||||||||||
| 153
- 26.05.2015 - 19:15
|
Ого, съездила к клиенту на полдня, а тут такое...:) Паша, ты не думай, что я прям до тебя докапываюсь, но я тебе объясню, что мне кажется не так. Я взяла твою фразу "На Кавказии считается, что трек прошел через что-то, когда он прошел в километре от точки" и посчитала, что ты говоришь так применительно именно к базе треков. А там у тебя "районирование" довольно условное, поэтому я и сказала, что это не так. Но, оказывается, ты имел в виду базу топонимов. Ок, пойдем в базу топонимов. Что не так, или может, я не знаю, как пользоваться - -- объекты не алфавитном порядке, а не понятно в каком, как искать? - фильтра по району нет. Пусть даже районы такие общие, как Лагонаки, Тхачи, но вот не хочу я смотреть весь список, если мне нужен только район Большой Лабы. Взяла одну из точек из майского похода - г.Б.Пцицер. Вуаля - ни одного трека http://caucasia.ru/site/toponim/993 Объяснимо - на кавказии действительно нет близко расположенных треков. Дубль 2 - г.Магишо http://caucasia.ru/site/toponim/985 Треков нет(кроме границ заповедника). Необъяснимо, т.к. неподалеку проходят 2 трека, один из них мой и я гарантирую, что он помог мы пройти на Магишо Потому что мало это, что 1 км, что 2 км. А вот лист 500-метровки уже зацепил бы некие объекты, которые бы могли стать отправной точкой к планированию. А так нет почти никакой наводки на то, откуда логично идти на Магишо. Хотя видя список ближайших объектов хочется ткнуть в кордон Закан. Ок, ткнём... И о, чудо, это ж как раз тот самый кошмар, когда наложены друг на друга куча одинаковых треков, там и по цветам не поймешь, какой из них где. http://caucasia.ru/site/toponim/2170 Если ты считаешь, что такой интерфейс удобен, то у нас с тобой просто разный взгляд на понятие удобства поиска. | | ||||||||||||||||||
| 154
- 26.05.2015 - 19:28
| 153 - База топонимов Кавказии не доработана (и там только кубанские). Я вообще все это время вел речь не про нее. А про алгоритм поиска треков, проходящих мимо чего-то, использованный там. Этот алгоритм подходит и для задачи топикстартера в шапке темы. Только и всего. Мой основной тезис - не надо ничего складывать по папкам или переименовывать! Надо просто запустить такой скрипт, который реализует то, что реализовано на топонимах кавказии, только у себя в папке на диске (если не хочется с сайтами связываться) - и получится ответ на начальную задачу. Никакие другие пришедшие мне на ум способы не подходят (или они чем-то значительно хуже). | | ||||||||||||||||||
| 155
- 26.05.2015 - 19:29
| Если вам надо готовое решение, я могу написать такую программу за час. Но она будет на Perl (по историческим причинам другими языками программирования не пользуюсь), и вам на Windows придется поставить ActivePerl (но это не сложнее, чем установить Java). | | ||||||||||||||||||
| 156
- 26.05.2015 - 19:30
| Цитата:
1. Добавить треков 2. Сделать не 1 км, а 10 км Не вижу проблем :))) | | ||||||||||||||||||
| 157
- 26.05.2015 - 19:32
| Цитата:
| | ||||||||||||||||||
| 158
- 26.05.2015 - 19:36
|
Еще раз напишу свой тезис, чтобы вы понимали с чем спорить :) Итак, автор спросил: Цитата:
"Предлагаю технический способ - некая программа, реализующая на диске пользователя поиск треков, проходящих в N км от интересующего района (в виде точки, при желании расширить район можно просто задать несколько точек). Похожий алгоритм реализован в разделе "Треки рядом" страницы "топонимы" Кавказии. Я могу написать такую программу, но она будет на перле (и скорее всего понадобится база данных умеющая SQL, можно без нее, но тогда написание займет больше времени)." Теперь ищите что здесь не так и спорьте. | | ||||||||||||||||||
| 159
- 26.05.2015 - 19:39
|
Еще раз - Кавказию в этом контексте не обсуждаем, там нет решения задачи господина wayerr (тем более что он не хочет закачивать в интернет все эти треки). там просто используется похожее решение, которое можно использовать и для задачи wayerr у него на компьютере. Кавказию можно обсуждать, чтобы улучшить то, что там сейчас есть (уже по итогам этой темы я наметил там несколько улучшений, которые неплохо было бы сделать в ближайшее время). Но к задаче wayerr и моим предложенным вариантам ее решения, это не относится. | | ||||||||||||||||||
| 160
- 26.05.2015 - 19:56
|
А алгоритм в целом такой (подходит и для 10 треков и для миллиона треков): A. Однократно: 1. Сканируем один раз все имеющиеся треки, определяем вокруг каждого описанный прямоугольник, заносим его координаты в базу данных вместе с именем/номером этого трека. B. Каждый раз при поиске: 1. Задаем координаты целевой точки, рядом с которой надо найти треки. (в случае Кавказии в базе есть координаты т.н. "топонимов" - они и берутся, в случае отдельной программы можно вводить с клавиатуры для простейшего консольного варианта или кликать мышкой для продвинутого гуишного) 2. Делаем запрос в базу данных, возвращающий все треки, внутрь описанных прямоугольников которых попала наша целевая точка 3. Для каждого отобранного трека открываем файл с треком, определяем число точек, если их слишком много - прорежаем (берем не каждую, а каждую вторую, третью, а еще лучше каждую N/100-ю - смотря как реализуем), для каждой просмотренной точки трека определяем расстояние до целевой точки - при таком масштабе можно по эвклидовой-пифагорийской формуле (корень из суммы квадратов катетов), если нашлась точка с расстояним меньшим N км - выводим имя файла такого трека - он нам подходит. Все. Это универсальный алгоритм, когда треков очень много и будет еще больше. Чтобы один раз просканировать свою базу треков в поиске нужных, конечно, не нужна никакая база и можно убрать пункты A.1 и B.2 - они тут только для ускорения ("оптимизации"). | |
Интернет-форум Краснодарского края и Краснодара |
