![][1] Для автомобилистов проблему незнакомых улиц давно решили навигаторами. Но даже автомобилисты ходят пешком. Если магазин через дорогу, то мы встаём и идём. Трудности появляются, если предстоит пройти пятьсот метров по незнакомой улице и два-три раза свернуть. Ни один из известных нам сервисов не строил маршрут из точки А до точки Б там, где нет тропинок и тротуаров, зато полно заборов и домов причудливых очертаний. 2ГИС решил эту проблему. Мы научились строить маршруты для пешеходов по растеризованной карте местности. Карта формально представляется [ графом ][2]с вершинами на регулярной решётке в местах, где пешеход может находиться физически. Принято считать, что такой способ строить маршруты неприемлем, потому что съедает много ресурсов. Под катом — как мы с этим справились. [Читать дальше →][3]

[1]: https://habrastorage.org/files/aa0/26f/3cd/aa026f3cd53a49ee8e84313daca75891.png
[2]: https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
[3]: http://habrahabr.ru/post/266753/#habracut