В этом разделе представлены алгоритмы поиска максимальной окружности вписанной в выпуклый многоугольник. Первый из них делает это за время 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 находится здесь.
|