HPC.ru lite - Все форумы
Форум: PocketGPS Pro и MacCentre PocketGPS
Тема: Странно, карта новая, а маршруты старые...
Страницы: 1 [2] 3

[Ответить]
VctOs [31.10.2003 16:43] Re: Это ОШИБКА программы.:
Я не готов обсуждать здесь теоретические основы программирования, замечу лишь о том, что понятие оптимальности алгоритма и оптимальности результата это две очень разные вещи.

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

Любой алгоритм работает с моделью мира в соответствии с формулировкой поставленной задачи. Правильными обычно считаются алгоритмы, результат которых соответствует ограничениям модели мира и формулировке задачи, неправильными - остальные.

Выбор метода поиска стартовой дуги осуществлялся с учетом существующих реализаций в т.ч. по западным системам с учетом следующих соображений:
*Результаты учета пересекаемых объектов в подавляющем случае не влияют на результат расчета, и в любом случае компенсируются опцией автоматической перепрокладки маршрута.
*Учет всех препятствий приведет к невозможности прокладки маршрутов от любых точек, расположеных вне дорог (например любой выезд из точки, расположенной внутри квартала требует пересечения препятствия типа "бордюрный камень", внутри кварталов существуют точки, из которых невозможно провести отрезок прямой к дуге дорожной сети не пересекающий препятствие категории "здание").
*Ряд категорий препятствий (наземные линии метро, заборы, подъездные ветки железных дорог) согласно действующим нормам
не подлежат открытому опубликованию на картах.
Предложенный Вами способ улучшения программы за счет наложения ограничений на пересечение при въезде / выезде на ближайшую дугу объектов типа железные дороги и водоемы в принципе реализуем, но он потребует дополнительных затрат времени (необходимо найти все пересекаемые отрезком выезда / съезда объекты местности) на каждую прокладку маршрута и не гарантирует возможность беспрепятственного выезда на ближайшую дугу.
В любом случае благодарю за Ваше замечание и не могу не отметить факт того, что начал размышлять над этой проблемой ядра.

По моему - все же не свидетельствуют:
В описании алгоритма я отмечал то, что "Въезд" и "выезд" на ближайшую дугу осуществляется по воздушной прямой без учета существующих на местности и изображенных на карте препятствий
Алгоритм работает в соответствии с описанием, т.е. правильно.
VladNew [31.10.2003 17:25] :
Ну послушайте, о чем Вы говорите. К чему эта заумщина? Простому обывателю-пользователю глубоко наплевать, как там эта программа строит свой алгоритм - ему просто нужна надежная система для навигации. И кому, скажите на милость, захочется держать в голове все эти допущения алгоритма и как там эти дуги вяжутся с бордюрами и секретностью пост-советских карт. Мне все-таки кажется, что если уж программа претендует на звание навигационной, то она таковой и должна быть. Сейчас в ней слишком уж много всяких ограничений и допущений. Зачем она такая выпущена в свет была, если нужно сверяться с бумажной картой постоянно и/или игнорировать ее сообщения (типа разворота на 180 на 3-т кольце через бордюр), которыми только самоубийца мог бы следовать?
d2003 [31.10.2003 18:26] :
Я тоже хочу внести свою лепту в модификацию алгоритма прокладки маршрута. По моему, необходимо внести поправку при проезде перекрестков и особенно разворотах. Т.е. каждый узел в котором пересекаются больше двух дуг должен считатся как виртуальная дуга с определенным весом и длинной , завясящие от количества дуг, весов дуг по которым проходит наш маршрут по отношению к весам остальных дуг (т.е. когда мы едем по большой дороге с большим весом, а перекресток с маленькими дорогами, то вес виртуальной дуги таких перекрестков высокий и длинна маленькая, а если наоборот, то и вес такого перегрестка очень мал с большой длиной)
Ну и разворот соответственно.
Я думаю что это решит многие проблемы.

Дмитрий
Alikante [31.10.2003 18:48] Касательно воздушных путей.:
Я конечно извиняюсь, может я чего резко сказал, меня просто на этой неделе адреналин задолбал.

Что критично. Алгоритм, использованный в обсуждаемой программе - не единственный.
В других известных мне алгоритмах (Smartpath, Tom-Tom, ПАЛМГИС и используемый в машинах Опель) проблемы "право-лево" при пересечении (в 2-D) текущей позиции с будущим маршрутом не существует.
Как не существует проблемы указаний системы "правее-левее" в условиях отсутствия пересечений пороезжих частей.

Нет в них также регулятора плотности точек маршрута.

За то там есть переключение оптимизации длины маршрута с использованием, как вы выражаетесь, "пошлин" на использование просто длины пути без всяких пошлин.

Эта разница объясняется тем, что, как я понимаю, вышеописанные системы дают рекомендации по маневрам ТОЛЬКО при приближении к пересечениям проезжих частей. В случае, когда системы оборудована дифф. сигналом, позволяющим определять в какой полосе осуществляется движение, даются также рекомендации заранее перестроиться, чтобы успеть совершить необходимый маневр.

В случае, когда, например, автобан не имеет съездов, как бы не петляла сама дорога (например автобан Запад-Восток в Швейцарии или автобан Монте-Карло - Ницца), система молчит, пока вы не начнете приближаться к указанному в проложенном маршруте съезду.
Там есть еще одна хорошая функция. Если вы засомневались правильно ли вы едете, вы нажимаете кнопку "Подсказка пути" и ласковый женский голос говорит вам расстояние до ближайшего поворота - например : "Через 20 миль на перекрестке с круговым движением третий поворот налево" (в Англии)

Употребленное вами слово "воздушное" многое объясняет в идеологии системы. Мне кажется ее изначально делали для авиации. Так как если все это давать в 3-D, то по таким указаниям очень удобно сажать самолет вслепую в полном тумане ночью при выключенных огнях на ВПП. Тогда, действительно, надо отслеживать все изгибы трассы движения. На земле же, в авто, такая плотность точек избыточна. Она только ресурс КПК сжирает.
Поэтому-то программе не хватает памяти проложить маршрут от Бронниц до Шереметьево. Хотя на том же КПК, другая программа легко прокладывает маршрут от Парижа до Варшавы.

Может к движку "плотность точек маршрута" добавить флажок "Только пересечения проезжих частей"?

И вообще, есть ли смысл трахаться с доводкой алгоритма Лазер-мэп, если он был разработан для других целей? Может лучше купить готовый алгоритм от Том-Том или какой еще? Может тот же ПалмГисовский? Никому же в голову (кроме совсем отчаянных) не приходит сегодня писать новый Windows для коммерческих целей. Написать то можно, но писать и отлаживать будешь очень долго и угрохаешь кучу денег на это. При всех недостатках этих самых Окон, вероятность того, что новая система такого же масштаба окажется лучше, не слишком велика.
Хороших вам выходных
VctOs [31.10.2003 19:02] :
Но ведь по-моему все (по Москве) уже реализовано именно так как Вы предлагаете.
Вот пример типового перекрестка:
http://www.77.ru/pics/gastello.gif
Каждый из возможных на этом перекрестке маневров изображен в виде дуги. Для каждой дуги в специальной таблице хранится пошлина (вес дуги). Учитывать узловые пошлины или количество пройденных узлов при такой топологии неверно, т.к. затраты времени на совершение маневра уже учтены в пошлинах соответствующих дуг.

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


Мне наоборот кажется, что многие проблемы были бы решены переходом к линейно-узловой топологии (с сворачиванием перекрестков в точку и учетом стоимости проезда узла независимо по каждому из возможных направлений), но доказать я это не имея подготовленных данных не могу, удобного софта для подготовки данных у картографов нет, времени на создание нового графа придется потратить уйму, число ошибок после пересоздания графа неизбежно возрастет и есть вероятность того, что использовать такие данные можно будет только в одной программе.
Alikante [31.10.2003 19:15] Касательно маршрута:
Показанные на картинках перлы - это круто. Особенно на Лениградке. Хотя у меня, кажется, такого хулиганства прога себе не позволяла.
Но на Ярославке, насколько я помню, предложенный в ПокетеГПС вариант возможен?

Я не об этом.

Даже при правильном маршруте блок голосовых и визуальных подсказок путает право\лево. И это способно создать аварийную ситуацию на дороге.
VladNew [31.10.2003 19:33] :
Вот в чем я согласен с Alikante, и о чем я говорил все время уже раз сто - зачем "писать Windows" заново? Вместо того, чтобы сочинять и испытывать на живых людях всякие свои программы, приобретите лицензию на дистрибуцию нормального продукта, и сидите себе спокойно деньги собирайте. И никого раздражать так не будет и ответственность минимальна. Возьмите ту же Ostia (простите, если кого утомил, но это единственная программа, которой я пользовался до ЖПС-а). А если уж хочется улучшить чего-нибудь, то начните с карт.
VctOs [31.10.2003 20:05] :
Да что Вы говорите?
Какое у Вас избирательное зрение, однако!
Специально для людей с проблемным зрением привожу наглядно два примера развязок с одного маршрута, описанного выше. Таких примеров можно привести достаточно. Для сравнения этот же маршрут, проложенный упомянутой выше программой. Надеюсь, картографов из ИНГИТа Вы не причисляете к дилетантам? Или Вы уверены, что автомобилисты в здравом уме предпочтут Ваши варианты маршрутов?
P.S. Движение справа налево.
Еще раз повторяю:
1)Давайте быть друг к другу корректнее
2)Я проверял Ваши сообщения: алгоритм на них работает правильно и находит оптимальный маршрут.
Например, по выезду Ярославка - МКАД-СЕВЕР:
Маршрут по верхней эстакаде: 135 секунд (751 метр со скоростью 20 км/час)
Движение по Ярославке от точки ответвления верхней эстакады - под мостом МКАД, по дуге на МКАД и по МКАД до точки примыкания верхней эстакады:
Ярославка: 22[с] + 8[с] + 14[с] = 44[с]
Дуга: 35[с]
МКАД: 2[с] + 5[с] + 5[с] + 14[с] = 26[с]
ИТОГО: 44[с]+35[с]+26[с] = 105[с]

Аналогично - для съезда с внешнего МКАД на Библиотечный проезд
Правильный на местности вариант проходит через дуги с весами:
9+7+6+33+11+31+33+35=165[с].
Неправильный на местности, но оптимальный с точки зрения алгоритма, ничего не знающего о местности кроме нарисованных на карте дуг и заданных в таблице пошлин проезда по ним:
46+38+8+19+14=125

Я понимаю, конечно, что пользователю абсолютно фиолетово из-за чего неверно прокладывается маршрут и приношу извинения за причиненные неудобства, но все чем я могу помочь в этой ситуации - написать о проблеме в соответствующем форуме
http://194.87.12.72/forum/viewtopic.php?t=204
VctOs [31.10.2003 21:51] Re: Касательно воздушных путей.:
бывает

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

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

Нет. Воздушная прямая - это ГИС термин не имеющий отношения к авиации. Траектория захода на посадку в авиации называется по-моему глиссадой.
Соответственно неверны Ваши последующие выводы о плотности точек и т.д. Насколько я понимаю ситуацию, ползунок регулирует плотность точек в которых будут подаваться подсказки. Моя следующая гипотеза - эти точки (с подсказками) на экране PocketGPS отмечаются кружочками

Память для прокладки маршрута в ядре выделяется однократно и ее объем не зависит от расстояния между стартом и финишем. Т.е. если памяти не хватает нельзя проложить никакой маршрут. Поэтому я отмечал эту причину как менее вероятную.

Ничего не могу сказать по этому поводу

Так уж сложилось исторически, что в мире КПК прокладка маршрутов в ЛазерМап появилась до создания Том-Том и появления ПалмГИС. Правда, после перехода на новое поколение карт с количеством дуг графа дорожного движения порядка четверти миллиона алгоритм прокладки маршрута пришлось полностью переписать (как и многое другое), но как мне кажется от этого он не стал хуже.

Аналогично.
VctOs [01.11.2003 10:49] :
Смею заметить, что Ваш вопрос был адресован конкретному лицу: "Не мог ли бы мне объяснить уважаемый г-н Кокос...", поэтому с моей стороны на него отвечать было как минимум невежливо. Тем не менее изложенные Вами факты я промоделировал на стенде 24 октября для того, чтобы проверить, не вызваны ли они неверной работой функций ядра.

Извините, а почему скорость на эстакаде считается равной 20 км/час?
135 секунд, 751 метр и 20 км/час это значения, взятые из аттрибутивных полей дуги эстакады. Достоверных сведений, почему скорость принята равной 20 км/час у меня нет: назначение времени движения по дуге (пошлины) в беззаторной ситуации выходит за рамки алгоритма поиска оптимального маршрута.

Здесь оправдано говорить лишь о расхождении в данных для расчета. По моему личному мнению, если обсуждать совокупные характеристики качества картографических баз данных по Москве и области от фирмы Ингит и фирмы Геоцентр-Консалтинг, последняя намного превзойдет первую. Даже по опубликованым Вами скриншотам видно, что пространственные данные о развязках в Ингит не обновлены со времен перестройки МКАД, а обсуждаемая нами эстакада дорисована "от руки". Что касается граблей с топологией - смею уверить, что в "улицах Москвы v.4 2003" их сильно не меньше чем на карте Геоцентра и тому есть объективные причины: очевидно, что из Питера отслеживать Москву полевыми методами значительно сложнее.

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

Я в свою очередь пользуясь случаем хочу напомнить о том. что вероятность исправления ошибок на карте существенно повысится, если сообщения о них публиковать на специально созданном для этого форуме: http://194.87.12.72/forum/viewforum.php?f=2
[Ответить]
[< Назад]  [Вперед >]