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

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

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

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


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


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


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

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

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

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

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

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

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

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