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

Question

Для заданных наборов 2D точек, которые являются границами неправильной формы, формы, которая не может быть выпуклой и может иметь внутренние отверстия, существует ли алгоритм для нахождения наибольшего круга, который соответствует границам?

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

Answer 1

Проблема не очень хорошо определена, так как множество точек не ограничивает какую-либо область.Граница, которую вы упоминаете, должна быть некоторой кривой, вероятно, многоугольником.Без этого нельзя сказать, что есть внутренние дыры, а также нельзя попросить, чтобы круг находился внутри границы.С помощью этого определения вы можете создать круг любого размера «снаружи», который касается нескольких заданных точек.

Если вы используете полигон для указания границы, ссылка Aioobe будет хорошей.Если вы переопределите задачу, чтобы найти круг с максимальным радиусом, касающийся, по крайней мере, 3 точек данного набора, то это будет то же самое, что проверка на наличие окружностей Триангуляция Далауне .

Answer 2

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

Так или иначе, альфа-формы имеют тесное отношение к диаграмме Вороного точек, которая является двойственной (в виде плоского графа) к триангуляции Делоне .

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

В двойной установке триангуляций Делоне этот узел соответствует треугольнику Делоне с наибольшей окружностью.

Это решение также мотивировано проблемой максимального вписанного круга в вычислительной геометрии.

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

Анализ и внедрение. Временная сложность алгоритма составляет O (n log n) для диаграммы Вороного и O (n), чтобы найти узел Вороного с наибольшим клиренсом. Классическая реализация - qhull . Кажется, есть реализация C ++ в boost , которая сделает это за вас. Но любой код триангуляции Делоне тоже подойдет.

Возможные проблемы. Если форма похожа на букву Омега, которая имеет большой карман, то узел Вороного с наибольшим зазором находится «вне» формы Омега. Следовательно, нужно было бы лучше понять понятие «внутри» и «снаружи» выбранной формы. Здесь снова может помочь изначально упомянутая альфа-форма, ср. опрос , проведенный Эдельсбруннером, который изобрел альфа-формы.

Answer 3

Очень тупой алгоритм :) (вероятно, возможно что-то более быстрое)

Самый большой круг должен касаться как минимум 3 объектов (объект является либо вершиной, либо линией).

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