company_banner

Сколько математики нужно, чтобы подписать многоугольник в JS API Яндекс.Карт

    В JS API Яндекс.Карт существует возможность создавать различные объекты на карте. Один из их них – многоугольник, с помощью которого можно улучшить интерактивность пользовательской карты: выделить отдельные области или отобразить местоположение неточечного объекта. К примеру, так можно показать план строительства нового квартала или зоны доставки пиццы.

    У пользователей API Яндекс.Карт давно появился вопрос о добавлении подписей поверх многоугольников. Люди предлагали хитрые решения, чтобы добавить подпись на объект в нужном месте, скрыть ее, перекрасить и т.п., но такие решения получались сложными и негибкими.

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


    Отображения региональных слов из словаря Даля, т.е слова которые ищут значительно чаще, чем в среднем по России

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

    Создать подписи к многоугольникам — одна из рутинных задач. Можно сидеть и отрисовывать все в фотошопe, но это получается максимально не гибко:

    • Любые изменения содержимого (значения в подписях, цвет) поведут за собой изменение всех подписей, надо будет отрисовывать каждую заново.
    • Полноценное взаимодействие с картой включает в себя смену масштабов, для которых не всегда можно разместить читаемый текст на карте в многоугольнике. Размера многоугольника может не хватить для полного отображения подписи на определенных масштабах, следовательно необходимо для каждого отрисовывать подписи разных размеров.

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

    Отображения самых популярных слов в запросах о разных странах

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

    Выбор алгоритма для определения подходящего центра для подписи


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

    Для решения задачи поиска центра существует несколько алгоритмов:

    Расчет положения по центроиду


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


    Так выглядит результат определения центроида. Видно, что точки на Хабаровском и Камчатском краях попали в неблагоприятное для отображения подписи место.

    Полюс недоступности или точка самого большого вписанного круга




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

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

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

    Как происходит поиск


    Алгоритм построен на основе дерева квадрантов. То есть для исследуемого многоугольника строится область (квадрант), в которую полностью помещается многоугольник. Далее эта область делится на четыре равные части и так далее рекурсивно с каждым квадрантом.



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



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

    Результат работы алгоритма




    Видно как отличается точность алгоритмов: “центр” на “проблемных” многоугольниках стал подходить намного лучше для расположения подписи:

    • Красные точки — центроид
    • Зеленые — полюс недоступности



    После выбора алгоритма для нахождения “центра” многоугольника, мы начали работу над модулем подписывания.

    Алгоритм работы модуля


    Подписывание многоугольника происходит в несколько этапов.
    На вход модулю отдается коллекция, в которой находятся вершины многоугольников для подписывания.

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



    Далее перед нами стоит задача понять, вмещается ли подпись в многоугольник.
    Модуль достает шаблон подписи и на его основе создается HtmlElement.

    objectManager.add({
          ...
          options: {
                labelLayout: '<h1>{{properties.name}}</h1>'
          },
          properties: {
                name: 'nameOfMyPolygon'
          }
    });
    



    Далее модуль дожидается загрузки картинок из тегов , если таковые присутствуют, и с помощью getBoundingClientRect() вычисляются размеры этой подписи. К сожалению, не существует методов, которые могли бы сказать о размере не вставленного в DOM элемента. Поэтому сначала надо подпись отрендерить. А для того, чтобы при получении размера не было “миганий” (показа и скрытия подписи), она отрисовывается в специальном контейнере, который скрыт от глаз пользователей.



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

    objectManager.add({
          ...
          options: {
                labelLayout: '<h1>{{properties.name}}</h1>',
                labelOffset: [80, -50]
          },
          properties: {
                name: 'nameOfMyPolygon'
          }
    });
    



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

    objectManager.add({
          ...
          options: {
                labelLayout: '<h1>{{properties.name}}</h1>',
                labelOffset: [80, -50],
                labelPermissibleInaccuracyOfVisibility: 10
          },
          properties: {
                name: 'nameOfMyPolygon'
          }
    });
    



    Полученные координаты переводятся в географические и проверяется, поместилась ли подпись в многоугольник.



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

    Возможности модуля


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

    Одной из важных задач была — сделать удобный способ вставки макета в многоугольник. С помощью специальной опции можно задать в виде строки html-макет, который поддерживает базовый синтаксис языков шаблонов Twig/Django Templates.

    У каждого многоугольник существует два вида подписи: основная и маленькая.



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

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

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


    Слева — автоматический центр, справа — установлен на координаты [72, 92]

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


    Отступ по 30px сверху и слева


    Погрешность в 25px

    Не обошлось дело и без стилей, есть возможность менять размер и цвет текста или же задавать значение атрибута class.

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

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

    Не остались без внимания события. Все события, произошедшие с подписью (нажатие, наведение...) пробрасываются на родительский многоугольник и соответствуют базовым событиям в API, нужно только добавить перед ними “label”.

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

    Дизайн и интерфейс решения


    Зачастую, текст является одной из основных частей подписи, поэтому мы уделили ему отдельное внимание.

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


    Изображения сверху: обычный текст, без обводки
    Изображения снизу: два стандартных стиля модуля

    Многострочные подписи не очень хорошо читаются при выравнивании текста по левому краю, поэтому было поставлено центральное выравнивание дефолтным.



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



    Гибкий макет подписей пригодится и для инфографики, например, показать флаги стран мира или гербы областей.



    Итак, что у нас получилось


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

    Заключение


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

    Для тех кому стало интересно


    Чтобы начать использовать модуль, необходимо выполнить пару пунктов из инструкции в данном репозитории.

    Пример


    jsfiddle.net/51qtdx3a/5

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

    Яндекс

    765,00

    Как мы делаем Яндекс

    Поделиться публикацией

    Похожие публикации

    Комментарии 15
      +2

      А отмасштабировать координаты (скажем, поделить x на 5-10) перед поиском полюса недоступности не хотите? Вам ведь важнее "широкие" места, а не "высокие".
      Или перед поиском прогнать эрозию с маской в виде горизонтального отрезка длиной L-H (L и H — оценка длины и высоты надписи).

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

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

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


          В плане быстродействия — интуитивно кажется, что если брать не слишком высокое разрешение (скажем, 64*64 "пикселя" для куска карты, включающего наш полигон) — то алгоритм "распространения волны" от края (сейчас не вспомню его название, давно с таким возился — лет 10 назад уже, наверное… что-то вроде волнового алгоритма, но пути вычисляются так, что от точки волна бежит с круглым фронтом) даст решение не медленнее, чем вся эта процедура с quadtree, а погрешность будет приемлемая.


          А ещё — предполагаю, что если считать полюс недоступности не по наибольшей вписанной окружности, а по наибольшему вписанному квадрату, результат не станет заметно хуже, но быстродействие вырастет весьма заметно (для варианта с растровым изображением — вообще получается простой волновой алгоритм, очень быстрый, без floating point)


          Но это всё так — просто обсудить другие решения и модификации вашего. Раз у вас уже есть работающее решение — вряд ли оправдана его замена.

        +8
        Каак? как вы смогли это и без машинленинга и нейросетей? )
        Шутка.
          +1
          Барнаул — самое популярное региональное слово в Барнауле. Так и запишем. (=
            +1

            Могли бы Mapbox и с большой буквы написать, господа из яндекс.карт.

              0
              исправили, спасибо
              0
              а если искать полюс недоступности не для окружности, а для овала с соотношением радиусов, зависящим от соотношения ширины/высоты текста?
                0
                На КДПВ есть «Оле» — это явно было "… Йошкар-Оле", по какому принципу обрезали название города?
                  0
                  Модуль не обрезает слова и показывает подпись в том виде в котором передашь.
                  КДПВ — картинка с исследований, и оно такое слово хотело отобразить.
                  +1
                  Спасибо, очень интересно!
                    +2
                    Спасибо за статью. Наконец-то что-то о применении алгоритмов и математики в реальной жизни, что даже я понял.
                      +2
                      Когда-то давно (лет 15 назад) решали подобную задачу для подписи проекций областей видимости видеокамер на карту местности. Такая проекция (в конкретной реализации) — это почти выпуклый многоугольник, который состоит не более, чем 255 вершин. Как он получается — это отдельная история и там много нюансов (например, если стоит здание, то часть области на условную поверхность земли не проецируется, а уходит в бесконечность). Почти — это значит, что геометрический центр всегда будет внутри многоугольника, хотя многоугольник при этом может и не быть выпуклым.

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

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

                      Так, казалось бы простая задача, потребовала необычных исследований и расчетов. Было интересно.
                        0
                        Извините, что сюда, но вопрос есть. Яндекс собирается что-то делать с этим?

                        image

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

                      Самое читаемое