Переход к шагу 5. Шаг
Переход к шагу 5.
Шаг 4. Точка t не является внутренней точкой Q2. Если «смотреть» из точки t, то многоугольник Q2 лежит в клине с углом, меньшим или равным ?. Этот клин определяем двумя вершинами u и v многоугольника Q2, которые находим за один обход вершин многоугольника Q2. Вершины u и v разбивают границу Q2 на две цепочки вершин, монотонные относительно изменения полярного угла с началом в точке t. При движении по одной цепочке угол увеличивается, при движении по другой - уменьшается. Одну из этих цепочек удаляем (ее точки являются внутренними относительно строящейся оболочки). Другая цепочка и граница Q1 являются упорядоченными списками, содержащими не более N вершин. За время, пропорциональное O(N), их можно соединить в один список вершин, упорядоченный по полярному углу относительно точки t.
Шаг 5. К полученному списку точек применяем метод обхода Грэхема. Затраты времени пропорциональны O(N).
Итак, утверждение. Выпуклая оболочка объединения двух выпуклых многоугольников находится
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
