Навигация по развилкам: to VctOs

[Пикс]

Я не понимаю гаишника, который стоит там на островке и просто закрывает глаза на то, что народ игнорируя все знаки уходит с Садового налево на Каретный Ряд. И это не только "синие", либо мигалки. Это же просто залотое дно должно быть для него. Либо деньги не нужны, либо сами правила не знают, либо уж не знаю...

[VctOs]

Они по прежнему генерятся по алгоритму, который не ориентирован на общий случай. Поэтому время от времени он генерит подсказки вводящие в заблуждение.

Предлагаю всем вместе попросить Вячеслава Чепракова довести результат нашего коллективного предварительного исследования до разработчиков подсказок с просьбой сообщить, получается ли у них воспроизвести описанную Вами проблему (а еще лучше оттолкнуться от сообщения Аллигатора от Ср Авг 24, 2005 17:52 "движение по Ленинградке из центра, около Сокола, через тоннель на Ленинградское шоссе.
Подсказка "возьмите правее" - если бы не знал, что надо в тоннель, уехал бы мимо" - там явно что-то не то с направлением)

Поймите меня правильно, я не могу гарантировать, что в ядре нет ошибок, но для того, чтобы их устранить мне требуется как минимум знать о них. В обоих обсуждаемых случаях я по графической отладочной информации, полученной на настольном компьютере считаю, что развилок, на которых были бы основания предлагать предлагаемые маневры нет. И вполне могу предположить, что коллеги считают, будто это ядро дает неверные развилки, на основании которых генерятся неверные подсказки, а значит у них нет повода для беспокойства. Тема неверных подсказок, генерируемых в точках местах из которых можно выехать только в одном направлении и никуда более тянется настолько долго, что я не вижу более актуальных задач. Хотя не буду спорить с тем, кто напомнит мне о том, что приоритезация задач разработки PocketGPS Pro это не мое дело.

Я этой опции месяца 4 ждал,

А я ее реализацию в программе жду с декабря 2003-го.

[Чайни]

Logout написал верно. В алгоритм трассировки маршрута ползунки не входят и сведения об их настройке при трассировке не учитываются. Маршрут прокладывается на основании топологии и пошлин ребер графа, с учетом......

Тогда вообще не понимаю, зачем ползунок нужен... Ведь если программа прокладывает маршрут и знает вершины графа (а "вершина" - это точка графа с кол-вом входящих рёбер > 2), то почему даются подсказки между вершинами ???
Точнее, если вопрос сформулировать корректно, то звучать он будет так :
если есть маршрут, проложенный через вершины графа, то зачем вообще нужно фиксировать изменение направления ребра между вершинами ? Т.е. почему "тупо" не пропускать (при выдаче подсказок) всё, что лежит между вершинами ?

[VctOs]

Терминология теории графов:
Теория графов - область дискретной математики, объектом изучения которой являются графы.
Граф - математический объект, заданный множеством вершин (syn - узлов) и набором ребер (syn - дуг).
Ребро, дуга - упорядоченная или неупорядоченная пара вершин.
Маршрут в теории графов это путь между вершинами графа, проходящий вдоль ребер.
---------------
Развилка в моей терминологии - это вершина графа, из которой _выходит_ более одного ребра.
В последней версии ядра есть особый признак разворота, позволяющий из множества развилок выделить подмножество таких развилок из которых исходят только две дуги - одна вперед по маршруту и вторая назад в противоположном текущему маршруту направлении, т.е. по ребру по которому мы пришли в развилку по проложенному маршруту.

А "точки графа с кол-вом входящих рёбер > 2" пока никак не учитываются ядром и признаков, позволяющих классифицировать точки маршрута по этому свойству ядро не выдает.

[Чайни]

Развилка в моей терминологии - это вершина графа, из которой _выходит_ более одного ребра.......
А "точки графа с кол-вом входящих рёбер > 2" пока никак не учитываются ядром и признаков, позволяющих классифицировать точки маршрута по этому свойству ядро не выдает.

Сложности определения таких точек и последующего их пропуска при построении маршрута ? Ведь мне кажется, и задача построения маршрута была бы проще, и проблема подсказок не существовала бы в принципе, если бы алгоритм построения маршрута пропускал "промежуточные" вершины (т.е. те, к которым подходит 1 или 2 ребра).
Или я ошибаюсь, и "не всё так просто" ?

[VctOs]

Развилка в моей терминологии - это вершина графа, из которой _выходит_ более одного ребра.......
А "точки графа с кол-вом входящих рёбер > 2" пока никак не учитываются ядром и признаков, позволяющих классифицировать точки маршрута по этому свойству ядро не выдает.

Сложности определения таких точек и последующего их пропуска при построении маршрута ?

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

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

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

Или я ошибаюсь, и "не всё так просто" ?

Скорее я непроходимо туп.

[Alikante]

К сожалению я уже подзабыл терминологию теории графов. По этой причине мне никак не удается четко сформулировать только что высказанную в ветке мысль - все точки маршрута из которых число исходящих дуг меньше или равно 2 - должны игнорироваться при прокладке маршрутов и, особенно, при генерации подсказок. На мой взгляд, "безальтернативные" точки-вершины, с точки зрения прокладки маршрута и навигации, - информационный шум.
У меня вообще ощущение, что существующий алгоритм подсказок писался для использования при движении по записанному треку (пройденный путь). Например если вы, не имея карты в Гармине просто напишете трек, то чтобы по нему потом ехать существующий алгоритм подсказок - довольно удобен.

[VctOs]

Как это игнорирование должно выглядеть при трассировке маршрута?
Спрямлением непрямого участка дороги описываемого последовательностью таких точек до отрезка прямой линии?
Или есть способ лучше которого я пока не понимаю?

[Alikante]

С точки зрения маневрирования по маршруту (не считая маневров, вызванных действиями других участников движения) кривизна дуги между двумя вершинами графа, где число дуг более 2-х, которые мы стали называть "развилками", значения не имеет.
Это как включение поворотника на дороге с одной полосой движения - как бы дорога не петляла - его не включают, пока не съезжают с нее на перекрестке.
Понятно, что для генерации оптимального маршрута нужна длина каждой дуги между развилками и значения пошлин ограничения скорости по знакам и пробкам. Но вот кривизна - это информационный шум. Эта кривизна нужна только для отображения маршрута на экране. Если взять нав. системы, где карта с маршрутом не отображается - а только стрелки-подсказки и голос - то там этой задачи нет вообще. А оптиальный маршрут есть.
На мой взгляд у вас (если вы для прокладки маршрута обрабатываете промежуточные точки, в которых нет развилок) программа перегружена ненужными вычислениями.

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

Срочно убеждайте Макцентр менять алгоритм подсказок - он (по-хорошему) не для коммерческого продукта.

[VctOs]

Но вот кривизна - это информационный шум. Эта кривизна нужна только для отображения маршрута на экране. Если взять нав. системы, где карта с маршрутом не отображается - а только стрелки-подсказки и голос - то там этой задачи нет вообще. А оптиальный маршрут есть.

Кривизна имеет значение.
Маршруты АОВ и А'O'B' топологически отличаются только кривизной, но команды при прохождении развилки О(O') в них нужно подавать разные.

Срочно убеждайте Макцентр менять алгоритм подсказок - он (по-хорошему) не для коммерческого продукта.

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

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

Значит нужно добиться корректной поддержки добавленного чекбокса учета развилок.

[Чайни]

Нет, наверное я непроходимо туп
Язвить по примеру не буду. Буду говорить то, что есть, причём как программист, знающий, что такое "постановка задачи". Можно ? Спасибо.

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

[VctOs]

Нет, наверное я непроходимо туп
Язвить по примеру не буду. Буду говорить то, что есть, причём как программист, знающий, что такое "постановка задачи". Можно ? Спасибо.

На здоровье.
Я Вам выше по этой теме вопросов поназадавал о Вашей идее учета количества входящих в вершину дуг. Вам не интересно на них отвечать?

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

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

Необходима только длина дуги (для определения длины маршрута).

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

Кривизна нужна лишь для прорисовки маршрута.

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

Что касается приведённого примера, то определить направление движения на конкретном перекрёстке (вершине), а не изгибе дороги было бы гораздо более грамотно с точки зрения постановки задачи, ориентированной на пользователя, которого изгибы дороги (дуг) мягко говоря не интересуют (а для кого, в конечном итоге, делается программа ???), но его, пользователя, интересует проезд любого перекрёстка с правильным информированием.

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

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

Но чем именно Вам текущий алгоритм прокладки маршрута кажется некрасивым? Может быть Вы готовы "поставить задачу" на проектирование более "красивого" алгоритма прокладки маршрута?

[Alikante]

Прочитал я ответы VctOsa и расстроился.

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

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

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

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

[VctOs]

1) Прежде чем программировать прокладку маршрута неплохо изучить штурманское дело (для авиации или моря - не важно).

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

Маршруты, которые вы прокладываете существуют на планете Земля, координатная сетка которой существует довольно давно.
Задача, которую вы хотите решить в рамках последовательности точек (сетевого графа) имеет решение в географической системе координат.

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

Если представить, что на предложенной вами схеме Север находится наверху, то, с точки зрения навигации, разница между маневрами в развилке О и в развилке О' состоит в том, что вы подходите к одной из них курсом 90 градусов, а к другой курсом 0 градусов, при том, что из точек О и О' в точки B и В' курс один и тот же 0 градусов.

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

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

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

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

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

2) Тезис о том, что "Потребитель всегда прав", к сожалению, недальновиден. Позволяя Макцентру делать очевидные ошибки вы ставите под риск свою репутацию профессионала и рискуете вместе с Макцентром потерять рынок для своих услуг.

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

Тем более, что Гармин и Том-том уже тестируют свои системы на картах Москвы и области.

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

Мое ощущение от вашего ответа - у Макцентра в ближайшем будущем (1-2 года) не будет существенного прогресса в налаживании блока подсказок. Слишком глубоко непонимание проблемы.

Здесь Вы делаете неверный вывод исходя из неверной исходной посылки. Я - это не МакЦентр. Так что, если у кого и нет будущего - то по Вашей мысли это у меня, а не у МакЦентра.

[Чайни]

Я Вам выше по этой теме вопросов поназадавал о Вашей идее учета количества входящих в вершину дуг. Вам не интересно на них отвечать?

Во-первых, не вижу конкретных вопросов. Вы лишь написали, что я первый, кто счёл полезным определять 2 или больше дуг, входящих в вершину. Наверное, я первый заметил на улицах реальные перекрёстки Во-вторых, как я могу на это (если предположить существование вопроса) ответить ? Расписать алгоритм ? Написать программу ?

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

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

Потрясающе Вы - как всегда

Выше я писал что я понимаю под термином "развилка". Количество ребер в вершине может быть равно хоть сто, но при этом вершина не будет считаться развилкой до тех пор пока из нее не выходит ни одного ребра или выходит только одно ребро, поэтому предлагаю Вам дать определение Вашего понимания этого термина и при его использовании указывать на то, что это развилка в Вашем понимании. Иначе мы запутаемся в терминологии.

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

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

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

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

Но чем именно Вам текущий алгоритм прокладки маршрута кажется некрасивым? Может быть Вы готовы "поставить задачу" на проектирование более "красивого" алгоритма прокладки маршрута?

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


Если МАКЦЕНТР предложит поработать над постановкой задачи - не вопрос. Можно будет сделать не "лучшую неработающую" систему )))))))), а хорошую, надёжную и удобную, функциональность которой ориентирована на потребителя, а не на явно выпирающие заплатки.