Путаница на треугольной треугольнике и крупнейшем вписанном круге

Question

Мне нужно найти самый большой вписанный круг выпуклого многоугольника, я искал многие сайты, и я понимаю, что это можно сделать, используя триангуляцию Деланея. Я нашел в CGAL обсуждения на thread с помощью алгоритма с использованием CGAL:

Вы можете вычислить это легко с CGAL:

Во-первых, вычислить триангуляционную точек.

Затем итерации на всех конечных гранях триангуляции. Для каждого конечного лица ф

• вычислить его Окружность с
• найти с в триангуляции (для ускорения вещи, вы можете дать одну вершины е в качестве исходной подсказки для расположения точки)
• если лицо, возвращенное путем нахождения (c, подсказка), является конечным, тогда окружность c лежит в выпуклой оболочке точек, поэтому f является кандидатом
• , если f является таким лицом-кандидатом, вычислить его квадрат окружности keep только лицо с минимальным квадратом окружности

Руководство CGAL (глава 2D-триангуляция, а также несколько вещей из ядра) показывает каждую базовую функцию для этого.

Я был немного смущен последней частью этого алгоритма. Когда я читаю, то, что я понимаю из этого, состоит в том, что минимальный circumradius стороны триангуляции является радиусом для самого большого нераскрытого круга. Но из примеров многоугольника с триангуляцией Делоне, кажется, что даже маленькая окружность иногда не может уместиться внутри многоугольника, так как же она может иметь тот же радиус, что и наибольшая вписанная окружность?

Answer 1

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

Answer 2

Максимальный вписанный круг в многоугольниках. Классическое решение вычислительной геометрии для задачи с максимальным вписанным кружком для полигонов заключается в использовании граней, medial axis многоугольника. Этот подход работает в более общем виде, таком как полигоны с отверстиями, см. Этот вопрос stackoverflow answer.

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

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

Диаграмма Вороного с многоугольником с отверстиями (т. Е. Множество вершин и ребер) может быть вычислена в O (n log n) time, c.f. Fortune's algorithm (1986).Позже Chin et alii (1999) дал алгоритм O (n) для медиальной оси простого многоугольника.

Для выпуклых многоугольников, однако, время-оптимального алгоритм для диаграммы Вороного, которая работает в O (N) время было известно уже в 1989 году из-за Aggarwal et alii. Этот алгоритм следует в основном следующей идеей: Рассмотрим кривые смещения серого, движущиеся внутрь с единичной скоростью. Если спроецировать это движение в трехмерном пространстве, где ось г время вы получите блок-отстойные крышу над полигоном:

Эта модель крыши также можно охарактеризовать следующим образом: Поместите половинным пространство на каждом краю многоугольника при наклоне 45 ° с полигоном (таким образом, что они содержат многоугольник) и пересекают их все. Поэтому, если вы можете быстро вычислить пересечение полупространств, вы также можете быстро вычислить диаграммы Вороного выпуклых многоугольников. На самом деле, для максимальной задачи с вписанным кружком нам не нужно возвращаться к диаграмме Вороного, но возьмите один пик крыши, который обозначает центр максимальной вписанной окружности.

Теперь полупространства дуализированы точками, а затем пересечение полупространств соответствует выпуклой оболочке его двойственных точек. Aggarwal et al. теперь нашел алгоритм O (n) для выпуклой оболочки точек, вытекающих из этой настройки.

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

Простой & Быстрая реализация. Более простой алгоритм вычисления диаграммы Вороного мотивирован straight skeletons. Для выпуклых многоугольников диаграмма Вороного и прямой скелет совпадают.

Алгоритм реализации прямого скелета Stalgo в основном имитирует эволюцию структуры волнового фронта (кривые серого смещения). Для выпуклых многоугольников это сводится к нахождению последовательности краев.

Так простой O (п журнал п) алгоритм может выглядеть следующим образом:

1. Построить круговую список полигонов. Вычислите время срыва каждого края во время распространения волнового фронта и вставьте это событие в очередь приоритетов.
2. Пока очередь не пуста: выведите следующее событие с краем: удалите край из круговой структуры и обновите времена срыва соседних краев удаленного края.

На самом деле, вы можете упростить описанный выше алгоритм: вам не нужно обновлять обрывы краев в очереди приоритетов, но просто вставлять новые: поскольку новое время краха ребер строго ниже, вы всегда получаете право сначала, и отпустите остальных, а очередь не станет больше 2n. Следовательно, вы не ставите под угрозу сложность времени O (n log n).

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

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