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

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

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 градусов, начиная с точки, которую вы тестируете. См. Расстояние от точки до луча или сегмента.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Грубая сила.

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

См. Главу 3 в моей магистерской диссертации для получения дополнительных сведений о вычислении равноудаленных локусов для три сайта.

Я реализовал кусок кода Python на основе cv2, чтобы получить максимальный / самый большой вписанный круг внутри маски / многоугольника / контуров. Поддерживает невыпуклую / полую форму.

import cv2
import numpy as np
def get_test_mask():
    # Create an image
    r = 100
    mask = np.zeros((4 * r, 4 * r), dtype=np.uint8)

    # Create a sequence of points to make a contour
    vert = [None] * 6
    vert[0] = (3 * r // 2, int(1.34 * r))
    vert[1] = (1 * r, 2 * r)
    vert[2] = (3 * r // 2, int(2.866 * r))
    vert[3] = (5 * r // 2, int(2.866 * r))
    vert[4] = (3 * r, 2 * r)
    vert[5] = (5 * r // 2, int(1.34 * r))
    # Draw it in mask
    for i in range(6):
        cv2.line(mask, vert[i], vert[(i + 1) % 6], (255), 63)
    return mask


mask = get_test_mask()

"""
Get the maximum/largest inscribed circle inside mask/polygon/contours.
Support non-convex/hollow shape
"""
dist_map = cv2.distanceTransform(mask, cv2.DIST_L2, cv2.DIST_MASK_PRECISE)
_, radius, _, center = cv2.minMaxLoc(dist_map)

result = cv2.cvtColor(mask, cv2.COLOR_GRAY2BGR)
cv2.circle(result, tuple(center), int(radius), (0, 0, 255), 2, cv2.LINE_8, 0)

# minEnclosingCircle directly by cv2
contours, _ = cv2.findContours(mask, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)[-2:]
center2, radius2 = cv2.minEnclosingCircle(np.concatenate(contours, 0))
cv2.circle(result, (int(center2[0]), int(center2[1])), int(radius2), (0, 255, 0,), 2)

cv2.imshow("mask", mask)
cv2.imshow("result", result)
cv2.waitKey(0)

Красный круг - это максимальный вписанный круг

Источник: https://gist.github.com/DIYer22/f82dc329b27c2766b21bec4a563703

Я использовал прямые скелеты, чтобы разместить изображение внутри многоугольника в три этапа:

1. Найдите прямой скелет, используя алгоритм прямого скелета (рис. 1).
2. На прямом каркасе найдите самый большой круг (фото 2).
3. Нарисуйте изображение внутри этого круга (фото 3).

Попробуйте это: https://smartdiagram.com/simple-infographics-3d-charts-2/

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

Бинарный поиск наибольшего радиуса R для окружности:

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