Наибольший круг внутри невыпуклого многоугольника

Ответ 1

Ключом к решению этой проблемы является сначала наблюдение: центр наибольшего круга, который будет помещаться внутри произвольного многоугольника, - это точка, которая:

• Внутри многоугольника; и
• Самый удаленный от любой точки на краях многоугольника.

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

Эта проблема возникает в географии и решается итеративно любой произвольной точностью. Его называют проблемой поляков недостижимости. См. Поля недоступности: Алгоритм вычисления для удаленных мест на Земле.

Основной алгоритм работает следующим образом:

• Определите R как прямолинейную область от (x _min, y _min) до (x _max, y _{maxсуб > );}
• Разделите R на произвольное число точек. В документе используется 21 как эвристический (разделить высоту и ширину на 20);
• Закрепить любые точки, находящиеся вне полигона;
• В остальном найдите точку, которая наиболее удалена от любой точки на краю;
• С этого момента определите новый R с меньшими интервалами и границами и повторите с шага 2, чтобы получить любой произвольный ответ точности. Статья сводит R к квадратному корню из 2.

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

Кроме того, что касается проверки расстояния до любого края, вам необходимо рассмотреть два случая:

• Точка перпендикулярна точке на этом ребре (в пределах границ двух вершин); или
• Это не так.

(2) легко. Расстояние до края - это минимум расстояний до двух вершин. Для (1) ближайшей точкой на этом ребре будет точка, пересекающая край под углом 90 градусов, начиная с точки, которую вы тестируете. См. Расстояние точки к лучу или сегменту.

Ответ 2

Алгоритм O (n log (n)):

• Постройте диаграмму Вороного краев в P. Это можно сделать, например, алгоритм Fortunes.
• Для узлов Voronoi (точек, равноудаленных трем или более ребрам) внутри P;
• Найдите node с максимальным расстоянием до ребер в P. Этот node является центром максимальной вписанной окружности.

Ответ 3

В случае, если кто-то ищет практическую реализацию, я разработал более быстрый алгоритм, который решает эту проблему для заданной точности и делает ее библиотекой JavaScript. Он похож на алгоритм итеративной сетки, описанный @cletus, но он гарантирует получение глобального оптимума и на практике в 20-40 раз быстрее.

Проверьте это: https://github.com/mapbox/polylabel

Ответ 4

Алгоритм O (n log X), где X зависит от требуемой точности.

Двоичный поиск наибольшего радиуса R для круга:

На каждой итерации при заданном радиусе r нажимайте каждое ребро E, "внутрь" на R, чтобы получить E '. Для каждого ребра E 'определим полуплоскость H как множество всех точек "внутри" многоугольника (используя E' в качестве границы). Теперь вычислим пересечение всех этих полуплоскостей E ', что можно было бы сделать в O (n) времени. Если пересечение не пустое, то если вы нарисуете круг с радиусом r, используя любую точку пересечения в качестве центра, он будет внутри заданного многоугольника.

Ответ 5

Резюме. Теоретически это можно сделать в O (n) времени. На практике вы можете сделать это в O (n log n) времени.

Обобщенные диаграммы Вороного.

Если вы рассматриваете вершины и ребра многоугольника как множество сайтов и тесселируете внутренность в "ближайшие соседние ячейки", вы получаете так называемую (обобщенную) диаграмму Вороного. Диаграмма Вороного состоит из узлов и ребер, соединяющих их. Зазор node - это расстояние до его определяющих поверхностей многоугольника.

(Здесь многоугольник даже имеет дырки, принцип все еще работает.)

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

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

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

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

Алгоритмы и реализации.

Фактически вы можете вычислить диаграмму Вороного. Наихудший алгоритм O (n log n) для точек и сегментов задается Fortune, алгоритмом Sweepline для диаграмм Вороного, SoCG'86. Held опубликовал программный пакет Vroni с ожидаемой сложностью времени O (n log n), которая фактически также вычисляет максимальный вписанный круг. И, похоже, реализация в boost тоже.

Для простых многоугольников (т.е. без отверстий) алгоритм оптимальной по времени алгоритма, который выполняется в O (n) времени, принадлежит Chin et al., Поиск медиальная ось простого многоугольника в линейном времени, 1999 г.

Грубая сила.

Однако, поскольку вы заявили, что у вас все в порядке с алгоритмом грубой силы: а просто попробуйте все триплеты сайтов (вершин и ребер). Для каждого триплека вы найдете кандидатов Voronoi узлов, т.е. Эквидистантных локусов на три сайта, и проверьте, пересечет ли какой-либо другой сайт максимальный вписанный круг кандидата. Если есть пересечение, вы отклоняете кандидата. Возьмите самое большое, что вы можете найти над всеми триплетами.

Подробнее о вычислении эквидистантных локусов для трех сайтов см. главу 3 в Мастер-тезис.