Comments 15
А отмасштабировать координаты (скажем, поделить x на 5-10) перед поиском полюса недоступности не хотите? Вам ведь важнее "широкие" места, а не "высокие".
Или перед поиском прогнать эрозию с маской в виде горизонтального отрезка длиной L-H (L и H — оценка длины и высоты надписи).
После выполнение операции эрозии мы получим уменьшенный полигон с симплифицированными границами, и в итоге на нем нужно все равно искать полюс недоступности, кажется, что это не ускорит процесс поиска.
Эрозия с маской-отрезком — это не для ускорения, а чтобы немного "сплющить" полигон по горизонтали — т.е. опять же чтобы предпочесть "широкие" места "высоким" (если масштабирование X ищет наибольший вписанный эллипс с заданным соотношением осей, то эрозия — для поиска наибольшего овала с длиной горизонтальных отрезков L-H)
В плане быстродействия — интуитивно кажется, что если брать не слишком высокое разрешение (скажем, 64*64 "пикселя" для куска карты, включающего наш полигон) — то алгоритм "распространения волны" от края (сейчас не вспомню его название, давно с таким возился — лет 10 назад уже, наверное… что-то вроде волнового алгоритма, но пути вычисляются так, что от точки волна бежит с круглым фронтом) даст решение не медленнее, чем вся эта процедура с quadtree, а погрешность будет приемлемая.
А ещё — предполагаю, что если считать полюс недоступности не по наибольшей вписанной окружности, а по наибольшему вписанному квадрату, результат не станет заметно хуже, но быстродействие вырастет весьма заметно (для варианта с растровым изображением — вообще получается простой волновой алгоритм, очень быстрый, без floating point)
Но это всё так — просто обсудить другие решения и модификации вашего. Раз у вас уже есть работающее решение — вряд ли оправдана его замена.
Шутка.
Могли бы Mapbox и с большой буквы написать, господа из яндекс.карт.
В математических терминах нужно было найти максимальный прямоугольник вписанный в такой «почти выпуклый» многоугольник. Использовали градиентный спуск для поиска максимума функции, начиная от геометрического центра. Нужно было искать и максимальный размер прямоугольника и оптимальную точку размещения его центра. Визуально результат был хорошим, но для большого количества объектов на карте, которые к тому же меняются со временем (камеры поворачиваются), алгоритм оказался не оптимальным и пришлось идти на некоторые ухищрения с кэшированием.
Уже позже случайно нашел научную статью, где такая задача решена за время, зависящее от количества вершин многоугольника. Но переписывать уже не стали, потому что и так все работало, да и процессоры стали быстрее.
Так, казалось бы простая задача, потребовала необычных исследований и расчетов. Было интересно.
Сколько математики нужно, чтобы подписать многоугольник в JS API Яндекс.Карт