OpenStreetMap *

TL;DR Очень подробный разбор алгоритмов решения задачи о кратчайшем пути от классики до двунаправленного А* и ALT с кодом и примерами на OSM

Люди пытались найти более быстрые способы передвижения на протяжении всей своей истории. Появление качественной дорожной системы в римской империи в своё время привело к её расцвету, но со временем выяснилось, что и в продуманных дорожных системах бывают забавные изъяны, как например в небезызвестной задаче о кёнигсбергских мостах, считающейся отправной точкой возникновения теории графов. Неудивительно и то, что с развитием вычислительной техники логистические задачи стали одними из первых, над которыми трудились первопроходцы компьютерных наук. Задача о кратчайшем пути -- одна из них, звучит достаточно просто: есть несколько городов и дорог, соединяющих пару городов между собой, мы хотим попасть из города А в город Б пройдя при этом минимальное расстояние. Первый системный подход к этой задаче был описан в работе Эгервари в 1931г., спустя 25 лет Эдсгер Дейкстра придумал алгоритм, который сейчас является частью любого уважающего себя базового курса алгоритмов на графах. На нём же, будем честны, заканчиваются знания о кратчайших путях у большинства профессиональных разработчиков, ибо сценариев, где реализации с википедии/stackoverflow будет не хватать, крайне мало.

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

_{⋮Дисклеймер:
Все нижеизложенное является лишь наблюдением и субъективной оценкой на основе личного опыта автора, а не утверждением.}

🔥 Примечание — эта статья автора расположилась на первом месте по рейтингу/просмотрам в хабе OSM за 2023г.

• Значки многочисленны: их более полутысячи, хотя некоторые варианты отличаются только цветом. Их каталог на сайте организован по категориям и подкатегориям. Все значки одной категории (если не перекрашены пользователем) имеют один и тот же цвет.
   
• Цвет внутренности значка может быть выбран свободно. Кроме того, пользователь может выбирать из семи различных стилей оформления внутренней части значка и внешнего контура, основывающихся на этом цвете:
  
  
   
• Набор значков каждого стиля можно скачать в ZIP-архиве, хотя внутри значки лежат простой кучею, а не по категориям.

Вступление

• OpenStreetMap
• OpenCycleMap
• OpenRouteService
• ShowYourJourney
• Проект Карты России
• MapOSMatic
• Веб интерфейс к GPSBabel
• CourseMapper
• GPS Visualizer

• Не знаю как вы, а я только что узнал, что в списке высокоприоритетных проектов Фонда свободного программного обеспечения (Free Software Foundation) находится создание свободной альтернативы Google Earth и Фонд призывает всех помогать проектам OpenStreetMap и Marble. Вы можете уже сейчас попробовать использовать свободную программу Marble со свободными картами OSM вместо проприетарного Google Earth.
• Если вы ещё не знаете, нас в России уже более 10 тысяч человек!
• Одна из самых популярных навигационных программ, Skobbler для iOS и Android стала бесплатной. Когда ещё приложение было платным, в Германии оно вошло в десятку наиболее часто скачиваемых в немецком интернет-магазине iTunes Store (150000 продаж за 6 месяцев).
• Специально подготовленные карты OpenStreetMap для вашего Kindle. Такое возможно проделать только с OSM.
• На сайте openstreetmap.org обновлена JavaScript-библиотека OpenLayers: теперь главный сайт OSM поддерживает устройства с тачскрином.
• Автомобиль без водителя проехал 20 км по центру города по картам OpenStreetMap (если я правильно понял, других источников не нашёл).
• Google снял видео о знаменитом проекте на базе OpenStreetMap.
• Участник OpenStreetMap встретился (видео) с министром правительства Москвы.
• Как рисовалась карта Калининграда на OpenStreetMap.
• "В школах до сих пор рисуют бумажные контурные карты. Скучное и бесполезное занятие. Лучше бы учили школьников пользоваться и пополнять OpenStreetMap".
• LearnOSM.org — простой пошаговый сайт, который научит вас делать карты с помощью OpenStreetMap.
• Состоялись встречи участников OSM в Кронштадте 1 октября (во встрече участвовало 24 человека) и во Владимире 17-18 сентября.
• И даже в Афганистане составляют карту OpenStreetMap и используют Android-приложение OsmAnd (возможно, это самая лучшая навигационная программа), написанное vics001 из Белоруссии.
• Прямой эфир свежих правок: где редактируют OSM прямо сейчас? См. "OSM Live", "khtml.org" или "GeoXP".
• «Туристические планы, информационные щиты, метровая карта на железнодорожном вокзале, буклет для гостиниц, флаер для путешественников» — приятные мелочи на основе данных OpenStreetMap в отдельно взятом городе.
• Компания 1Spatial и Университет Ноттингема будут совместно работать над OpenStreetMap.
• OSMоюмор: мечта о том, как все неровности дорог будут занесены в OSM и автомобили будут ехать плавно даже на неровных поверхностях.
• Это надо видеть: железнодорожный ад (источник).

• Открылся российский сайт OSM — openstreetmap.ru
• MapQuest пожертвовал 50 000$ OpenStreetMap Foundation (OSMF). Деньги в основном будут использованы на обновление и поддержку парка серверов в проекте OSM
• Управление города Эребру из Швеции первыми открыли свои геоданные под новой лицензией ODbL, которая требует указания авторства (attribution) и сохранения условий (share alike).
• Сейчас в OpenStreetMap добавляется примерно 90 000 км. дорог каждую неделю. Общее число дорог, нанесённых во всем мире является весьма впечатляющим с 24 млн. км и это отражает лишь около половины общего объема данных. Больше исследований можно найти здесь.
• User:SK53 создал карту, которая показывает плотность пабов на каждые 5 кв. км. в Великобритании
• Рендер 3D globe, который работает прямо в браузере с помощью WebGL, уже доступен. Посмотрите видео — впечатляет! Такой Google Earth только в браузере с картой OSM.

Пролог

• 24 марта участники OpenStreetMap за 24 часа попытались нарисовать карту Геленджика, известного нахождением там Мицгола, известного пиарщика Викимапии, т.е. фактически вторглись в логово врага конкурента. Результат вы можете увидеть сами.
• OpenStreetMap используют для отслеживания дворников в связи с чем кусочек карты OSM был показан по российскому телевидению.
• В Косово в результате войны правок, как сообщается, был уничтожен целый город — Митровица.
• 17 апреля начался третий этап перехода OpenStreetMap с лицензии Creative Commons BY-SA 2.0 на ODbL: все участники должны согласиться (или не согласиться как сделал я по нескольким причинам) с новыми условиями.
• Создан проект для распечатки карты в формате для бумажника со словами «давай встретимся вот в этом месте в случае ЧС».
• Карта ITO Map стала доступна во всём мире. Она показывает данные, которые скрыты на обычной карте OpenStreetMap, но информация присутствует в базе данных. Например, вы можете посмотреть количество полос на дорогах вокруг Москвы, метро и трамвайные пути в Петербурге, дороги с освещением, дома без указания высоты, электростанции, подстанции и линии электропередач с указанием напряжения, реки, ограничения скорости на дорогах, покрытия дорог.
• Завершён импорт базы данных домов Саратова. Результат можно посмотреть на карте.
• ОСМеры во всём мире отмечали 1 апреля: основатель проекта написал о закрытии OpenStreetMap, а поляки перевернули карту вверх ногами.
• Смоленск. "Удивительно, что такой большой, важный город, где даже есть трамвай и троллейбус, не родил ни одного осмера". Поэтому 21-22 мая в Смоленск на встречу съедутся участники OpenStreetMap со всей страны (а может и из Белоруссии и Украины) и нарисуют лучшую карту славного города Смоленск.
• Напоминаю, что скоро в Вене пройдёт самая близкая к России европейская конференция OpenStreetMap. Наши люди там будут иметь спич.