HPC.ru lite - Все форумы
Форум: PocketGPS Pro и MacCentre PocketGPS
Тема: Навигация по развилкам: to VctOs
Страницы: 1 2 [3] 4

[Ответить]
VctOs [28.08.2005 21:42] :
Сложности определения таких точек и последующего их пропуска при построении маршрута ?
Признаюсь, о сложностях задачи определения количества входящих в вершину дуг я еще толком не задумывался. Вы первый, кто счел этот параметр полезным. Я до сих пор не понимаю, какую пользу из него можно получить.

Чем была бы проще в таком случае задача построения маршрута?
Устроил бы Вас маршрут, построенных без "промежуточных вершин" (т.е. таких, к которым подходит 1 или 2 ребра)?
Как это может помочь снять "проблему подсказок"?

Скорее я непроходимо туп.
Alikante [29.08.2005 13:44] .:
К сожалению я уже подзабыл терминологию теории графов. По этой причине мне никак не удается четко сформулировать только что высказанную в ветке мысль - все точки маршрута из которых число исходящих дуг меньше или равно 2 - должны игнорироваться при прокладке маршрутов и, особенно, при генерации подсказок. На мой взгляд, "безальтернативные" точки-вершины, с точки зрения прокладки маршрута и навигации, - информационный шум.
У меня вообще ощущение, что существующий алгоритм подсказок писался для использования при движении по записанному треку (пройденный путь). Например если вы, не имея карты в Гармине просто напишете трек, то чтобы по нему потом ехать существующий алгоритм подсказок - довольно удобен.
VctOs [29.08.2005 15:32] :
Как это игнорирование должно выглядеть при трассировке маршрута?
Спрямлением непрямого участка дороги описываемого последовательностью таких точек до отрезка прямой линии?
Или есть способ лучше которого я пока не понимаю?
Alikante [29.08.2005 17:33] .:
С точки зрения маневрирования по маршруту (не считая маневров, вызванных действиями других участников движения) кривизна дуги между двумя вершинами графа, где число дуг более 2-х, которые мы стали называть "развилками", значения не имеет.
Это как включение поворотника на дороге с одной полосой движения - как бы дорога не петляла - его не включают, пока не съезжают с нее на перекрестке.
Понятно, что для генерации оптимального маршрута нужна длина каждой дуги между развилками и значения пошлин ограничения скорости по знакам и пробкам. Но вот кривизна - это информационный шум. Эта кривизна нужна только для отображения маршрута на экране. Если взять нав. системы, где карта с маршрутом не отображается - а только стрелки-подсказки и голос - то там этой задачи нет вообще. А оптиальный маршрут есть.
На мой взгляд у вас (если вы для прокладки маршрута обрабатываете промежуточные точки, в которых нет развилок) программа перегружена ненужными вычислениями.

В случае с картинкой на Соколе, похоже проблема та же с подсказками, что и у меня на Якиманке и у Северянинского моста - программа генерит подсказки исходя из изгиба (который видит в соответствии с заданной плотностью точек) поэтому игнорирует настоящую развилку и наводит на изгиб дороги после тоннеля или внутри его.

Срочно убеждайте Макцентр менять алгоритм подсказок - он (по-хорошему) не для коммерческого продукта.
VctOs [29.08.2005 23:12] :
Кривизна имеет значение.
Маршруты АОВ и А'O'B' топологически отличаются только кривизной, но команды при прохождении развилки О(O') в них нужно подавать разные.

Вы предлагаете это делать мне? МакЦентр в некотором роде является моим потребителем, а потребитель всегда прав. К тому же я не вижу, что можно в алгоритме генерации подсказок изменить на радикально. Развилки пусть и "с нюансами", но вроде учитываются. Точно, что МакЦентр не нужно убеждать в том, что учет развилок это гуд. С Вашей идеей отказа от учета геометрии промежуточных точек я пока сам не согласен. По-моему это вполне может вызвать новую волну столь полюбившихся всем советов запрыгивать на мосты над двухуровневыми развязками.

Значит нужно добиться корректной поддержки добавленного чекбокса учета развилок.
[К сообщению приложены файлы: kriv.jpg (11 кб)]
Чайни [30.08.2005 02:44] :
Нет, наверное я непроходимо туп
Язвить по примеру не буду. Буду говорить то, что есть, причём как программист, знающий, что такое "постановка задачи". Можно ? Спасибо.

Alikante абсолютно правильно говорит про отсутствие необходимости учёта "ложных" развилок (с кол-вом рёбер в одной вершине <=2) и про отсутствие какой бы то ни было необходимости в учитывании кривизны дуги при прокладке маршрута. Необходима только длина дуги (для определения длины маршрута). Кривизна нужна лишь для прорисовки маршрута.
Что касается приведённого примера, то определить направление движения на конкретном перекрёстке (вершине), а не изгибе дороги было бы гораздо более грамотно с точки зрения постановки задачи, ориентированной на пользователя, которого изгибы дороги (дуг) мягко говоря не интересуют (а для кого, в конечном итоге, делается программа ???), но его, пользователя, интересует проезд любого перекрёстка с правильным информированием. Вот эта задача не решена - программа полностью не делает того, что она обязана делать. К тому же, решение такой задачи менее ресурсоёмко, нежели задача определения направления движения в каждой точке маршрута.
"Примочки" в виде ползунка и чекбокса "Только развилки" - лишь попытки приблизить к "правильно работающей системе" конечный продукт. В итоге получились заплатки, не исправляющие ситуацию с неправильно генерируемой системой подсказок, основанной на... скажем так - на не продуманном до конца, не "красивом" алгоритме прокладки маршрута. Отсюда и абсолютно (не побоюсь этого слова) неверно работающая система подсказок.
VctOs [30.08.2005 10:13] :
На здоровье.
Я Вам выше по этой теме вопросов поназадавал о Вашей идее учета количества входящих в вершину дуг. Вам не интересно на них отвечать?

Извините, но то, что Вы написали в этом абзаце называется флудом - наполнением обсуждения лишними репликами, уводящими от темы. Выше я писал что я понимаю под термином "развилка". Количество ребер в вершине может быть равно хоть сто, но при этом вершина не будет считаться развилкой до тех пор пока из нее не выходит ни одного ребра или выходит только одно ребро, поэтому предлагаю Вам дать определение Вашего понимания этого термина и при его использовании указывать на то, что это развилка в Вашем понимании. Иначе мы запутаемся в терминологии.
Мы с Alikante обсуждаем эту тему с октября 2003-го. В декабре 2003-го вышел первый апдейт ядра, которое выдавало признаки того, является ли каждая точка маршрута вершиной графа или это внутренняя точка ломаной линии дуги. В некотором роде это можно назвать учетом кривизны. С осени 2004-м ядро к каждой точке маршрута добавляет флаг - признак того, является ли эта точка вершиной графа из которой выходит более одной дуги. С апреля 2005-го ядро позволяет из всего множества развилок выделять такие в которых можно ехать только прямо по маршруту и только обратно по маршруту.

Уже только для этого нужно иметь сведения о промежуточных узлах и внутренних точках дуг.

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

Предложите, пожалуйста, конкретный алгоритм, который без учета кривизны дуги АО будет верно определять направление маневра в вершине О. По-моему математически без учета кривизны дуг граф АОВС топологически эквивалентен графу А'О'В'С', что опять же математически доказывает тщетность попыток разработать такой алгоритм, который бы в узле О маршрута АОВ выдавал без учета кривизны дуги АО подсказку налево, а в узле О' маршрута А'О'В' предлагал бы ехать прямо.

Но чем именно Вам текущий алгоритм прокладки маршрута кажется некрасивым? Может быть Вы готовы "поставить задачу" на проектирование более "красивого" алгоритма прокладки маршрута?
Alikante [31.08.2005 18:42] .:
Прочитал я ответы VctOsa и расстроился.

1) Прежде чем программировать прокладку маршрута неплохо изучить штурманское дело (для авиации или моря - не важно).
Маршруты, которые вы прокладываете существуют на планете Земля, координатная сетка которой существует довольно давно.
Задача, которую вы хотите решить в рамках последовательности точек (сетевого графа) имеет решение в географической системе координат.
Если представить, что на предложенной вами схеме Север находится наверху, то, с точки зрения навигации, разница между маневрами в развилке О и в развилке О' состоит в том, что вы подходите к одной из них курсом 90 градусов, а к другой курсом 0 градусов, при том, что из точек О и О' в точки B и В' курс один и тот же 0 градусов.
Поэтому угол поворота в одном случае будет 90 гр. налево, во втором 0 гр. (прямо).

Для определения угла поворота достаточно иметь справочник к точке О - под каким углом к меридиану подходят дуги от других вершин и какова длина этих дуг. (с точки зрения маневра имеет значение угол примыкающих к точке "О" 20-ти метровых отрезков подходящих дуг, которые, для простоты можно считать прямой линией ) Это можно сделать один раз при подготовке карты.
В таком случае кривизна самих дуг, сходящихся в точке О, вас абсолютно не интересует.

Это к вопросу об альтернативном алгоритме.
Вся остальная информация об особенностях кривизны дуги - шум, с точки зрения прокладки маршрута.

2) Тезис о том, что "Потребитель всегда прав", к сожалению, недальновиден. Позволяя Макцентру делать очевидные ошибки вы ставите под риск свою репутацию профессионала и рискуете вместе с Макцентром потерять рынок для своих услуг. Тем более, что Гармин и Том-том уже тестируют свои системы на картах Москвы и области.
Мое ощущение от вашего ответа - у Макцентра в ближайшем будущем (1-2 года) не будет существенного прогресса в налаживании блока подсказок. Слишком глубоко непонимание проблемы.
VctOs [31.08.2005 19:57] Re: .:

По-моему не прошло и недели с момента последней претензии о том, что используемый в программе алгоритм генерации подсказок слишком ориентирован на морскую навигацию, чтобы его можно было бы использовать на земле.
Вы действительно считаете, что в воздушном или морском штурманском деле можно найти более правильный или более эффективный алгоритм поиска кратчайшего пути на графе чем предложенный Дейкстрой?

Не спрашивайте меня в какой СК ядро выдает результат трассировки маршрута и как получается, что линия проложенного маршрута соответствует координатам движущегося по нему автомобиля. Я не отвечу.

Вопрос в том, почему мне приходится вместо прямого пути выбирать кривой. Если хотите, можно считать, что мы идем по фарватеру. Шаг влево / шаг вправо - киль на рифе. Кривизна важна?

Но ответьте мне, такие справочники для непрямых дуг расчитываются с учетом кривизны дуги или как?
Вот если бы мне кто такой справочник сказал где можно добыть для автодорог г.Москвы и Московской области, да если бы эту таблицу было бы реально в памяти КПК разместить и потом к ней эффективно обращаться за данными, то я бы тут же попросил бы преобразовать таблицу входящих и исходящих курсовых углов в таблицу кодов маневров для всех возможных комбинаций проезда каждого перекрестка.

А что думают о кривизне фарватера лоцманы? Кривизна - это только шум, или ее все-таки разумно время от времени учитывать?

Мне не удобно публично рассуждать об этом. С одной стороны Вы правы, существует такое понятие как "авторский надзор". Но во-первых, о существовании ошибок я могу судить только по сообщениям в этом форуме. Во-вторых, эти сообщения относятся к сервисам, выходящим за рамки текущих возможностей ядра. Но все это с меня ответственности не снимает. Завтра попробую позвонить договориться о совместной отладочной сессии.

Зачем тестирует? Навиком уже достаточно давно продает карты для Гарминов.

Здесь Вы делаете неверный вывод исходя из неверной исходной посылки. Я - это не МакЦентр. Так что, если у кого и нет будущего - то по Вашей мысли это у меня, а не у МакЦентра.
Чайни [01.09.2005 04:13] :
Во-первых, не вижу конкретных вопросов. Вы лишь написали, что я первый, кто счёл полезным определять 2 или больше дуг, входящих в вершину. Наверное, я первый заметил на улицах реальные перекрёстки Во-вторых, как я могу на это (если предположить существование вопроса) ответить ? Расписать алгоритм ? Написать программу ?

Извините, но то, что Вы написали в этом абзаце называется флудом - наполнением обсуждения лишними репликами, уводящими от темы.Потрясающе Вы - как всегда

Я действительно "непроходимо туп", потому что применить термин "развилка" к вершине (читай - "перекрёстку"), из которой выходит <= 2 ребёр (читай - "дорог"), мне в голову не приходило... Обычно "развилкой" (читай - "перекрёстком") называют место, в котором есть выбор направления движения, т.е. к которому подходят хотя бы 3 дороги : по одной водитель въезжает на перекрёсток, по одной из двух (или больше) выезжает.

В остальном и без меня Alikante всё правильно пишет. Можете продолжать ему язвить От этого неправильно работающая система не станет правильно работающей. Вы при этом практически не слышите советы и обсуждение проблем сводите либо к непониманию (или нежеланию понимать), либо к откровенным попыткам язвить (что не способствует улучшению программы)

Теория графов сама по себе - ничего без практического применения в реальных условиях. В реальных условиях, по которым ездят пользователи/водители, перекрёсток c входящей на него одной дорогой и исходящей из него одной дорогой не бывает. Это просто дорога, на которой, как сказал Alikante, поворотник не включается. Это же очевидно, но вы чего-то пытаетесь доказать.

Но чем именно Вам текущий алгоритм прокладки маршрута кажется некрасивым? Может быть Вы готовы "поставить задачу" на проектирование более "красивого" алгоритма прокладки маршрута?В моём тексте принципиально первое предложение, а не последнее ) И про "примочки" важно Остальное - уже мелочи )
Так что... увольте
Кстати, о "заплатках"... сдвинул ползунок на максимум (отмечен чекбокс "только развилки"... или как он там называется). Поехал и понаблюдал. Ужас... Настолько отвратительно работающего сопровождения я не ожидал. Попытался сделать скриншоты, но подсказки-стрелки не записались почему-то... В PGPS screen4.jpg "Возьмите правее через 300 м" - абсолютно точная, но абсолютно бесполезная подсказка (как в анекдоте про программиста)
Второй вариант (PGPS screen3.jpg) - подсказка была бесподобна : "Возьмите правее через 300 м". Я ПРЯМО еду ! Мимо примыкания Семёновского вала - прямо, а уж дальше - налево. Но нет, меня хотели сбить с пути )))

Если МАКЦЕНТР предложит поработать над постановкой задачи - не вопрос. Можно будет сделать не "лучшую неработающую" систему )))))))), а хорошую, надёжную и удобную, функциональность которой ориентирована на потребителя, а не на явно выпирающие заплатки.
[К сообщению приложены файлы: PGPS screen3.jpg (21 кб), PGPS screen4.jpg (14 кб)]
[Ответить]
[< Назад]  [Вперед >]