Скажи мне, где ты, и я скажу тебе, где ты

    В подмосковном Подольске, в микрорайоне Силикатная-2, есть один лайфхак — когда на дворе уже 9 вечера, и пиво в магазинах уже не продают — достаточно просто перейти дорогу, чтобы его купить. Через дорогу Москва — в ней желаемое до 11 найти можно.

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

    Исторически на этот вопрос отвечает «обратный геокодер»(reverse geocoder). Он важная часть практически всех картографических АПИ — Google, Яндекс, и даже OSM. Но в большинстве случаев его ответ предназначается человеку, и содержит исключительно текстовое описание локации.

    Это-не-технологично! И уж точно непрактично. Esosedi, кушали этот кактус пару лет, а потом просто сделали свой обратный геокодер. Главное как и зачем.

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

    Часть 1.

    Так уж исторический сложилось, что esosedi это «места на карте мира». Олдскульные квадратики и привязкой к геокоординатам. Жаль только, что геокоординаты для нормальных людей просто набор чисел. Нормальным людям нужен адрес.

    Для перевода координат в адрес и используются «обратные геокодеры». Ты ему координаты, а он тебе некий адрес. Этого текста достаточно для понимания человеком расположения некого объекта. И, по человечески, никаких претензий к стандартным реализациям у меня нет. Но для «системы» это не подходит — тут и текстовый «матчинг» сам по себе не стабилен (и тормознут), так еще «нормальные» геокодеры ищут сразу по нескольким источникам, или по крайней мере по данным различных «провайдеров». Два запроса географически близких адресов могут быть найдены в разных базах, и ответы «текстами» друг с другом не состыкуются.

    А еще в ответах геокодера можно встретить и транслит, и орфографические ошибки, и даже разные системы сборки административного деления.
    Так например встречается иногда Город Москва, который Регион Город Москва, иногда еще и Городской Округ Город Москва, в котором сам Город Москва. Хотя чисто технически — это правильно. Нормализовано по образу и подобию других городов. Проблема в том, что иногда Москва — просто Москва, да и вообще по флагам в ответах она не город. Спасибо, что «Большую Москву» еще не придумали.

    Еще одна стандартная ошибки геокодера гугла — «притяжка» координат в улицам, не аккуратная работа с городскими округами, сокращения (Алтай Республиц), использование различных наименований местности. Россия может быть и Россией и РФ и нормальной Российской Федерацией.

    Я решил не ждать, когда за мной прийдут Аутономусы из Республики Чечения(всего 5 вариантов написания), и два года назад сделал свой геокодер на основе модуля регионов.

    Был наш — стал ваш. После случайного комментария в топике dadata геокодер стал публичным.

    Работает все просто — вы ему координаты, а в ответ получаете все osmRelationId, в которые эта точка входит. С разбивкой по административным уровням. Везде циферки, везде связь с другими источниками, везде «проверяемость».

    Для визуализации работы есть примерjsfiddle.net/azvjukh8, работа которого мне так понравилась, что теперь тоже самое красуется на главной esosedi.
    Алгоритм работы примера такой:

    • Берем текущий центр карты и отправляем запрос в геокодер.
    • Находим в ответе объект, размер которого нас устраивает.
    • Показываем его на карте. (На самом деле его родителя).
    • При движении карты — повторить.

    С момента выпуска osme многие люди меня просили облегчить поиск нужного региона — вот наконец и решается одна из проблем модуля подсветки административного деления — сложность найти нужный тебе «номер» региона. Ранее предлагалось идти на морду data.esosedi.org и искать там свое место рекурсивно погружаясь в пучины административного деления.

    Теперь все проще — jsonp ручка data.esosedi.org/geocode/v1?[lng=(ru|en)]&point=x,y[&seq=?][&callback=?] — работает 24 часа в сутки, 7 дней в неделю, с ограничением на 6* запросов в секунду средствами nginx…

    И позволяет, в среднем, делать в 3 раза больше запросов чем геокодеры АПИ Карт. А для тех кто сможет распределить нагрузку по фронтам (средствами DNS) выйдет примерно 20 RPS (+ burst x4).

    И самое главное — никаких домов и улиц, к которым может быть неправомерно притянута точка. А то иногда нормальная улица может находиться и в паре сотен километров от искомой точки, совершенно в другой стране. Только страны, кварталы, районы…

    Часть 2

    Геокодер работает на основе геометрии, которую отдает ручка регионов. Ему надо просто найти самый маленький полигон, куда входит точка, и все полигоны «выше». Но искать «выше» не надо — эта информация уже есть. Но собрал ее именно геокодер. Как уже говорилось — все это дело основано на геометрии OSM. Из OSM достаточно легко вытащить геометрию, но намного сложнее её переварить. Тем более склеить в четкую иерхическую структуру административного деления.

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

    Второй «узкий» момент заключается в том, что многие relation имеют неверный admin_level, или не имеют его вообще. Ну а флаг is_in(кто у кого в подчинении) вообще редкий зверь. В итоге самый надежный вариант — произвести геометрическую «пробивку» геометрии.

    На вход поступает полигон. Далее требуется найти некую точку внутри него и найти все другие полигоны, в которые эта точка входит. Отсортировать их по размеру и пересортировать в конечную административную вложенность — более мелкий обьект всегда входит в более крупный. С этим все четко.



    Итого задача разбивается на две:

    1. Быстро находить объекты, в которые входит точка.
    2. Быстро производить более точную проверку «PointInPolygon».

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

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

    Лично я решил проблему просто — я беру любую точку которая может входить в полигон, например геометрический центр, и проверяю ее «стандартным» алгоритмом.

    Стандартный алгоритм (Ray casting, O(n)) работает просто — из бесконечности слева в точку пускается луч, после чего считаются его пересечения с гранями полигона.

    Если пересекли нечетное количество раз — мы внутри. И точка нам подходит.

    Если четное — снаружи.

    И под конечную точку используем середину отрезка от первой точки пересечения до второй — она точно в полигоне.

    Всего на свете есть много алгоритмов для определения принадлежности точки полигону, с совершенно разной сложностью. Часть из них требует препроцесинг, часть — нет. Не тривиальные варианты или переводят полигон в более «математические» формы, снижая алгоритмическую сложность, или просто снижают N(количество вершин). Например любой, самый сложный, полигон можно просто разрезать на части. Для этого хорошо подойдет geojson-vt.

    Второй интересный момент — поиск минимального обьекта, который может пересекать точку. Чем меньше обьект — тем быстрее проверка. И точнее. Для этой цели хорошо работают Quad или R-деревья. Но это не особо лампово, посему давайте сделаем это через Z коды.

    Z код (N, Morton, Peano) — это число, полученное из 2Д координат (X,Y), такое что обьекты выше или левее всегда будут уметь его меньше, а правее и ниже — больше. Nested set.

    Фактически мы можем просто найти все обьекты, у которых один из уголов умеет Z координату больше искомой, и отсортировать по Z (у mapbox есть хорошая библитека, которая использует этот эффект — earcut).

    Хотя, если бы это работало — название у этих кодов было бы другое — Z код идет зигзагами. Когда мы попытаемся искать «ниже и правее» — его уведет налево. Спасает тут то, что под маской Z(оrro) скрывается bit interleaving. Из Z-кода через наложение маски всегда можно получить X или Y координату, и дополнительно ограничить поиск по ним… Ну и совершенно академическии можно найти точку «выхода» (LITMAX) из региона поиска и точку «входа» (BIGMIN). Этого, кстати, в earcut не хватает.



    В принципе использование «spatial filling curves» — это один из самых эффективных способов для 2D поиска, если у вас обычная база с циферками. Например MySQL. Хотя, меня до сих пор не покидает чувство, что PostGIS…

    Остается только загрузить из базы реальную геометрию, и произвести более точные вычисления. Тут возможны различные оптимизации, главная из которых лежит в основе данных OSM — не надо проверять полигон как полигон. Полигон это relation — набор отдельных сегментов. OSM это почти нормальная «топологическая» база данных. Можно проверять только маленькие сегменты, часто общие для двух вероятных ответов.

    Насколько это все быстро работает? — На рабочем ноуте при concurrency>10 получается порядка 600RPS. На боевых серверах с одной стороны быстрее, с другой стороны пинги до Германии — 60мсек.

    Итого на свете стало на еще один обратный геокодер больше. Он не такой как все — он «проверяемый»(термин википедии), выдает не только «текстовое» описание локации, но и ID, в том числе из разных баз, на которые можно опираться. Он не ищет дома, он не ищет улицы — только административную вложенность. (И только ту, что попала в текущую базу. Екатеринбурга, например, так нет — только городской округ.)
    Если вам нужен реально «нормальный» гекодер — возьмите Nominatim, который работает поверх OSM, или нормальные геокодеры нормальных АПИ Карт.

    … но тогда пропадет «дух охоты»....

    Если жив он в тебе, %username%, то жертва твоя — пример на фидле — jsfiddle.net/azvjukh8.

    Кому-то(dadata) такой геокодер может быть полезен для определения района улицы. Кому-то(калькулятор доставки) для фильтрации замкадышей.

    Кому-то(мне) он просто позволяет приятно проводить вечера.

    Документация по формату ответа доступна на https://github.com/esosedi/regions.

    Еще можно почитай немного теории, да практики:


    Или собери гекодер сам:



    PS: Ограничение на продажу алкогольной продукции сняли 18 декабря 2014 года (5 января 2015). Теперь по Области действуют федеральные нормативы. Но до магазинов в Подольске, как и до меня, эта новость не дошла.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 16
    • +1
      > когда на дворе уже 9 вечера, и пиво в магазинах уже не продают
      Странный лайфхак, в моём подмосковье уже давно до 23 продают. Наверное, у вас какое-то другое =)
      • 0
        Я только сейчас понял, что давно не видел таблички про ограничение продажи. При этом в биршопе после 21 на вынос не дают. Возможно это как-то связано с деталями лицензирования работы.
        Чтож, прийдется придумать другое романтическое обоснование обратного геокодера. Например нынче в Москве нельзя сверлить стены(и вообще шуметь) с 19, в то время как мой сосед без проблем может это делать(и делает) до 23.
      • +1
        Забавно. Я сейчас тихо-мирно тоже потихоньку пилю свой обратный геокодер (как библиотеку), который умеет возвращать то же, что и ваш (в смысле ID). Он переваривает все данные OSM примерно за полчаса и генерит бинарную базу примерно на 5Гб (могу еще сжать до 4Гб, но придется всякие битовые оптимизации мутить). После чего используя эту бинарную базу умеет порядка 100 000 локальных вызовов в библиотеку с временами ответов почти всех запросов в районе 1 микросекунды, если подтянуть все данные в память перед запросами. Честного тестирования производительности не делал, поэтому цифры примерные, но правильного порядка. Планирую в течении ближайших пары месяцев допилить и написать статью о библиотеке, алгоритмах и структурах данных в ней.
        • 0
          Я использую Osmosis для импорта planet файла — он только его переваривает в SQL 3-4 часа. Потом еще с неделю в полуручном режиме идет обработка и сборка данных.
          Насчет скорости — у меня есть код который держит все данные в подготовленном виде в памяти и работает очень быстро. Но у него есть две проблемы:
          1. У js вообще проблемы с обьемами памяти и бинарными структурами. Ну и с сам js для математики тоже не особо подходит :P.
          2. По правилам игры «ручка» АПИ на продакшен сервере не должна жрать ни память, ни проц.
          Буду ждать статью с нетерпением, успехов в теориях и практиках.
          • 0
            Полчаса — это если в 12 потоков) И код по хардкору на C++. Руками ничего не обрабатываю, потому что лень( Из-за этого всякие несуразности все-равно остаются.

            2. Это как-то неправильно. Задача обратного геокодинга сложная сама по себе, а если еще и память нельзя кушать, то совсем печально получается.
            • 0
              2. решается удлинением конвеера. В начале ищем конечную область, потом получаем данные, потом распаковываем первый кусок данных… Благодаря «асинхронности» интерфейсов nodejs можно держать одновременно сотню запросов на разных стадиях обработки. Каждый запрос обрабатывается медленно (10-20мсек), но обеспечивается очень высокое значение одновременно обрабатываемых запросов.
              В стрес тестах — на всех 12 ядрах — без проблем держалось ~500 одновременных запросов, которые выдавали 12к RPS на сервер. Потом http начинал валиться. Зажав скорость на уровне 5 RPS на клиента, я просто гарантирую работоспособность и бесплатность системы как для пользователей, так и для себя.
        • +2
          которую отдает ручка регионов

          Зашел в профиль, работает в Яндексе. Кто там у вас это первым придумал?
          • 0
            «Регионы» или термин «ручка»?
            • 0
              Термин «ручка» известен только Яндексоидам и тем, кому приходится с ними общаться. :)
              • 0
                Http сервис, endpoint, REST ресурс, интерфейсные хвосты, API и дырки…
                По некому адресу висит ручка… Её дергают.
                Спросил у людей вокруг, как это можно назвать «по-нормальному». Но их уже не спасти…
          • 0
            очень много геометрии в текущей базе просто нет, в частности многих городов, для которых кто-то почему-то (до сих пор) не создал relation.

            Екатеринбурга, например, так нет — только городской округ.

            Ваши две серьёзные ошибки:
            1) Геометрия может быть задано не только через отношение(relation), но и обычной замкнутой линией (way). Хотя для административных границ это скорее будет приятным исключением.
            2) Город (в плане населённого пункта) к административному делению не имеет никакого отношения, поэтому и искать его там не надо.
            А Екатеринбург, как населённый пункт вот.
            • 0
              К сожалению это моя боль. Где-то в дебрях OSM вроде даже есть рекомендация так не делать.
              Причина очень проста — в нормальной (и нормализованной) «топологической» базе данных город сложная система, и состоит из многих «way». Это должен быть «face», или relation. Вообще конечным обьектов должен быть relation.
              В 96% случаях это так и есть. Специально посчитал процент «потеряшек» без relation.
              Не смотря на то, что административное деление, острова разные и города существуют параллельно — их можно подружить. Просто забить на admin_level, флаги и смотреть на размеры. Да и есть в административке место городам. В разных странах по разному.
              Плюс я одинаковые объекты (Коломна, Малоярославец, Подольск, Париж) просто склеиваю в один. Хотя если Коломна и Малоярославец просто имеют ГО совпадающие с городом — чем отличаются два Подольска(1, 2) — мне не понять.
              • 0
                А чтобы не путаться, хотя бы в родной стране, полезно почитать основополагающие НПА, в частности
                131 ФЗ "Об общих принципах организации местного самоуправления в Российской Федерации"
                Поэтому выдав городской округ (ГО) за сам город, вы вводите пользователей в заблуждение, потому что в ГО кроме самого города могут находится другие населённые пункты. Понятно, что ~90% населения так же как и вы не заметят разницы, но выдавать это в сервисе как то не хорошо.
                • 0
                  Эээ нет. Я говорил о _точном_ полигональном соотвествии границ города и ГО. Такое наблюдается, например, в Коломне — она единственный населенный пункт своего муниципального образования.
                  Иногда ГО «чуть чуть» больше города, буквально на пару арков, но туда влезает пара деревень — это, конечно, уже другое. В норме сельские или городские округа(они же иногда районы) в сотни раз больше города(поселка, села) их образующего.
                • 0
                  Поэтому я бы вам предложил дополнить схему данных внутригородскими района (admin_level=9) и самими населёнными пунктами place=city/town/village/hamlet + возможно части города suburb
                  • 0
                    Сейчас средствами Osmosis выгружается:
                    административка — accept-relations boundary=administrative
                    острова и города — accept-relations place=island,town,city,village,borough,suburb --tf reject-relations boundary=administrative
                    «потеряшки» — reject-relations --tf accept-ways place=town,city,village
                    Suburb в потеряшках нет, так как нормальные районы нормальных городов идут через relation. Хотя… в тот же самом Подольске (или Екатеринбурге) их просто не нарисовали…

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.