Максимальная окружность вписанная в выпуклый многоугольник

В этом разделе представлены алгоритмы поиска максимальной окружности вписанной в выпуклый многоугольник.

Первый из них делает это за время O(n*log(n)) в худшем случае. Идея его следующая. Для каждой стороны и двух её соседних строим касательную окружность. Затем сторону с самой маленькой окружностью отбрасываем и пересчитываем окружности для её соседних сторон. Действуем таким образом пока не останется только три стороны. Для выбора минимальной окружности будем использовать конструкцию, которую называют пирамидой ( или heap ). Это массив указателей с номерами от 1 до n со следующим свойством: объект по указателю с номером i больше или равен объекта по указателю с номером i/2. Поэтому объект по указателю с номером 1 является минимальным. Подробнее об этом можно прочитать в "Искусство программирования" 3 том или "Алгоритмы. Построение и анализ" (Кормен, Лейзерсон, Ривест).

Def<Circle2d> maxCircle_NlogN ( CCArrRef< Line2d > & line );
Def<Circle2d> maxCircle_NlogN ( CCArrRef<Vector2d> & vert );

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

Следующий алгоритм находит окружность в худшем случае за время O(n2), но обычно быстрее, чем предыдущий. Вначале функция у которой параметром является массив вершин многоугольника ищёт перспективную вершину и начиная с неё определяет параметры прямых проходящие через рёбра. Затем вызывается функция у которой параметром является массив прямых. Там выбирается первое и последнее ограничения, и находится максимальная окружность, которая касается этих ограничений и лежит в многоугольнике. При этом определяется третье касательное ограничение. Если эти три ограничения образуют закрытый треугольник, значит найденная окружность является максимальной для всего многоугольника и на этом алгоритм заканчивается. Иначе часть рёбер отбрасывается и цикл повторяется.

Def<Circle2d> maxCircleInConvexPolygon ( CCArrRef< Line2d > &, nat & i1, nat & i2, nat & i3 );
Def<Circle2d> maxCircleInConvexPolygon ( CCArrRef< Line2d > & line );
Def<Circle2d> maxCircleInConvexPolygon ( CCArrRef<Vector2d> & vert );

В приложении DEMO можно посмотреть результат вписания.

Описание классов Line2d и Circle2d находится здесь.
Описание шаблона классов CArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Исходники алгоритмов находятся в файле opti2d.cpp.

Наверх