У меня есть набор непересекающихся прямоугольников, представляющих одну фигуру. Все края прямоугольника являются вертикальными или горизонтальными. Некоторые прямоугольники смежны, другие не пересекаются. Этот набор был получен путем вырезания одинаково ориентированных прямоугольников из одного другого прямоугольника. Как найти все точки, наиболее удаленные от краев новой фигуры?
Самым дальним, я имею в виду точку A в данном связанном многоугольнике P (поэтому мы игнорируем все непересекающиеся многоугольники, которые не содержат A; при условии отсутствия пересечения будет только один), такой, что существует нет точки B в пределах P, где минимальное расстояние от B до любой точки на краю P больше того же минимального расстояния с A.
Это то, что я думаю Я должен сделать:
- Группа смежных прямоугольников.
Преобразование нескольких смежных прямоугольников в один неправильный многоугольник, который является выпуклым или вогнутым и может содержать отверстия, но имеет только ортогональные края. Проблемы: как изобразить дыры? Должны ли отверстия быть удалены для (3)? Как удалить отверстия, сохраняя края ортогональными?
- Возможно, было бы проще выполнять шаги 1 и 2 параллельно.
Для каждого многоугольника примените алгоритм, который возвращает точку, наиболее удаленную от краев этого многоугольника, а также минимальное расстояние.
Фильтровать все точки, имеющие наибольшее минимальное расстояние; это результат.
Предполагая, что это правильно, какой алгоритм лучше всего сделать (3) и как он влияет на остальную часть ответа? Упрощается ли проблема только с вертикальными или горизонтальными краями?
Под лучшим я подразумеваю либо самый простой, либо самый быстрый.
Иллюстрация:
Редакт. V1:
Так что я решил эту проблему с помощью Google, чтобы найти несколько подходов
Алгоритмы
Диаграмма Вороного -> Средняя ось
Диаграмма вороного сегментов линии (а не точек) состоит из сегментов медиальной оси (линии или дуги параболы) и (рефлекторных) линий от каждой вершины многоугольника до вершины медиальной оси. См. этот ответ стекопотока (# 2) для обзора взаимосвязи между диаграммой вороного, средней осью и проблемой максимального вписанного круга. Также см. Ниже.
Использование «Алгоритм развертки для диаграмм Вороного» * 1079 *, O[n*log(n)].
Работает с выпуклыми или вогнутыми многоугольниками независимо от отверстий. Построить диаграмму Вороного для ребер многоугольника. К сожалению, производит неупорядоченный набор сегментов (линий или парабол). Организовать набор в графическую структуру, прежде чем определять максимальный вписанный круг. См. «Диаграммы Вороного и день на пляже» для хорошего обзора алгоритма состояния.
Использование «Нахождение средней оси простого многоугольника за линейное время» , O(n).
Работает с простыми многоугольниками (выпуклыми или вогнутыми) без отверстий. Это кажется очень сложным, поэтому я решил пропустить это.
Использование "Алгоритм линейного времени для вычисления диаграммы Вороного выпуклого многоугольника" , O(n).
Работает только для выпуклых многоугольников, поэтому не применимо к моей проблеме. Для получения дополнительной информации см. этот ответ стекопотока (# 1) .
Прямой скелет -> Средняя ось
Для выпуклых многоугольников диаграмма вороноя и прямой скелет одинаковы. Поэтому эти решения не применимы к моей проблеме.
- Используйте "STALGO" ,
O[n*log(n)]. См. этот ответ стекопотока (# 1) для получения дополнительной информации.
Грубая сила, O(n^4). См. этот ответ stackoverflow (# 3) и этот ответ stackoverflow (# 2) .
Для всех возможных трехсторонних комбинаций (порядок не имеет значения) ребер многоугольника и вершин:
Постройте максимальный вписанный круг для каждого набора, то есть найдите центральную точку, равноудаленную от всех трех.
Отменить результаты, если центр находится вне многоугольника.
Отменить результаты, если любое другое ребро или вершина находятся внутри (или пересекаются) окружности.
Сортировка по радиусу окружности; вернуть наибольший круг.
Триангуляция Делоне -> Диаграмма Вороного -> Средняя ось
Должна быть возможность преобразования из триангуляции Делоне в диаграммы вороного ... но я не рассматривал это для диаграмм вороного с ребрами . Этот подход может быть полезен, если ваша библиотека геометрии обеспечивает только триангуляцию Делоне.
Диаграмма Вороного и максимальный вписанный круг
Каждый ресурс, который я видел, утверждает, что максимальный вписанный круг касается трех граней (вершин или ребер) многоугольника, и поэтому центр максимального круга должен быть вершиной на средней оси. Но это только подмножество максимальных вписанных кругов. Рассмотрим среднюю ось прямоугольника:
Любой круг с центром вдоль горизонтального сегмента средней оси является допустимым максимальным вписанным кругом. Поэтому, если сегмент медиальной оси разделяет две ближайшие соседние ячейки, и соответствующие сегменты многоугольника этих ячеек параллельны, то вместо края всей средней оси представлен набор максимальных вписанных окружностей.
Интуитивно я думаю, что так оно и работает, учитывая возможные комбинации ребер многоугольника с ближайшими соседними ячейками:
линия, линия, параллель: медиальная ось - это линия, представляющая набор возможных максимально вписанных окружностей.
линия, линия, а не параллель: средняя ось - это линия. Как обычно, конечные точки этой линии должны иметь как минимум две рефлекторные линии, соединяющиеся назад с многоугольником. Возможный максимальный вписанный круг центрирован на конечной точке с самой длинной рефлекторной линией.
линия, точка: медиальная ось - парабола. Как и выше, используйте рефлекторные линии, чтобы определить центр возможного максимального вписанного круга. (*)
точка, точка: То же, что и выше. (*)
Не уверен насчет последних двух
И вот почему метод грубой силы, описанный выше, является неполным.
Ортогональные многоугольники
Несмотря на ортогональное ограничение, я не смог найти более простых алгоритмов построения медиальной оси. В одной статье это ограничение использовалось для обеспечения более устойчивых альтернатив медиальной оси: «Скелетные представления ортогональных форм» .
Редактировать v2:
Интересно, можно ли каким-то образом адаптировать этот подход к переполнению стека - на основе "Полюсы недоступности: алгоритм вычисления для самых отдаленных мест на Земле" - для моего ввода ( зеленые) прямоугольники (вместо квадратов), гарантируя абсолютный максимальный вписанный круг.