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

Question

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

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

Answer 1

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

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

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

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

Основной алгоритм работает так:

1. Определить R как прямолинейную область от (x _min , y _min ) до (x _max , y _max );
2. Разделите R на произвольное количество точек. В статье в качестве эвристики используется 21 (что означает деление высоты и ширины на 20);
3. Обрезать любые точки вне полигона;
4. Для остатка найдите точку, наиболее удаленную от любой точки на краю;
5. С этого момента определите новый R с меньшими интервалами и границами и повторите процедуру, начиная с шага 2, чтобы получить любой произвольный точный ответ. Бумага уменьшает R в квадратный корень в 2 раза.

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

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

Грубая сила.

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

См. Главу 3 в моей Магистерской диссертации , чтобы узнать больше о вычислении эквидистантных локусов для трех сайтов.

Answer 5

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

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

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