На рис. 8.11 показаны оба случая. При обработке живого ребра aft после обнаружения того, что точка b является сопряженной к нему, добавляем к списку построенных треугольников треугольник ajb. Затем ищем ребро fb в словаре. Поскольку оно обнаружено впервые, то его там еще нет и состояние ребра /Ь изменяется от спящего к живому.
Перед записыванием ребра fb в словарь, перевернем его так, чтобы примыкающая к нему неизвестная область лежала от него справа.
Ребро Ьа в словаре уже есть. Так как неизвестная для него область (треугольник aß) только что была обнаружена, это ребро из словаря удаляется.
Функция hulIEdge строит ребро, принадлежащее границе выпуклой оболочки convS. В этой функции фактически реализован этап инициализации и первой итерации метода "заворачивания подарка". s
8. Основные алгоритмы вычислительной геометрии
Функция mate определяет, существует ли для данного живого ребра е сопряженная ему точка, и, если она есть, находит ее. Для того чтобы понять, как работает эта функция, рассмотрим множество окружностей, проходящих через концевые точки ребра е. Центры всех этих окружностей лежат на срединном перпендикуляре к ребру.
Рассмотрим процесс "надувания" окружности, проходящей через е. Если в результате такого "надувания" окружность пройдет через некоторую точку из набора то эта точка является сопряженной к ребру е. в противном случае ребро сопряженной точки не имеет.
Быстродействие данного алгоритма равно 0(п2).
Упражнения
1. Покажите, что разность х$ъ - хъуи равна площади (со знаком) параллелограмма, определяемого векторами а = (xitva) и b = (хьУь)2. Напишите функцию, которая проверяет, является ли данный многоугольник выпуклым.
3^ Покажите, что любая точка выпуклого многоугольника с вершинами vb v2, vn может быть записана в виде a\V\ +…+ anvn, где а\ +…+ яп= 1 и. а\ ^0, ап ^0
4. Напишите функцию для нахождения пересечения двух выпуклых многоугольников р и q, работающую за время 0(пр + nq).
5. Диаметр набора точек определяется как максимальное расстояние между любыми двумя точками набора. Напишите функцию, вычисляющую за время 0(nlogn) диаметр набора из п точек плоскости.