исходного набора,
исходного набора, образующих невырожденный треугольник; тогда любая его внутренняя точка нас устроит (по существу, берутся “первые попавшиеся” две точки, а третья отбирается при последовательном выборе, т.е. с трудоемкостью O(N));
*
либо найти средние арифметические значений координат Xi и Yi всех точек и приписать их, соответственно, новой (внутренней!) точке - A(X,Y); очевидно, вычисления имеют ту же трудоемкость - O(N)).
Переопределим координаты всех точек исходного набора в полярной системе координат, принимая за начало координат точку A; нулевой угол отсчета можно связать с любым лучом, в частности, выбрать для этого луч AX1. Очевидно, трудоемкость обработки вновь составит O(N). Отсортируем по неубыванию точки исходного набора, используя в качестве ключа значение полярного угла, причем при равенстве углов будем “отсеивать” точки с меньшим расстоянием от начала координат; в результате получим набор N1?N. Трудоемкость обработки, если воспользоваться “быстрыми алгоритмами” сортировки, составит O(N logN). На последнем этапе осталось отсеять точки, которые не войдут в выпуклую оболочку. Для этого осуществим последовательный перебор троек “соседних” точек упорядоченного набора N1, отсеивая лишние - до получения искомого набора Ncover. При этом, для каждой очередной “тройки” проверяем значение угла между ними pi-1pipi+1: если угол не меньше 180°, то точка pi исключается из набора N1 и новая тройка “начинается” с той же точки pi-1; в противном случае индекс i увеличивается на 1. Перебор завершается, когда обход “по кругу” не приводит к отсеву точек: Ncover сформирована.
<<< Предыдущий урок
| Новости | Регистрация | Курсы | Карта сайта | Контактная информация |
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
