Алгоритм построения выпуклой оболочки с использованием метода сортировки
Задано множество точек S(p1,…,pN), для которого произведена лексикографическая сортировка по x и y. Т.е.   .
если:
· Либо Y1 < Y2
· Либо Y1 = Y2 и X1 < X2
· Точки, Y-координаты которых совпадают, называются уровнями.
Будем считать, что точки расположены так, как показано на рис. 11.1:
Рис. 11.1.
Примечание:
Pmin_x – множество точек из множества S таких, что координата Х – минимальна
Pmin_y – множество точек из множества S таких, что координата Y – минимальна
Pmax_x – множество точек из множества S таких, что координата Х – максимальна
Pmax_y – множество точек из множества S таких, что координата Y – максимальна
Множество точек Pmin_y находятся на M-уровне
Множество точек Pmax_y находятся на 0-уровне
Разобьем множество точек на квадранты.
Построим выпуклую оболочку для I- квадранта. (Для остальных квадрантов оболочка строится аналогично).
Шаг 1: из множества точек {Pmin_y} выбираем ту, координата Х которой максимальна. Обозначим ее pi(X1,Y1)
Шаг 2: из множества точек {Pmax_x} выбираем ту, координата Y которой минимальна. Обозначим ее pj(X2,Y2)
Шаг 3: Среди точек множества S, ищем точку p(X1,Y) (на уровне M-1 или выше), такую что для любого X1 больше X. Обозначим ее как pr
Рис. 11.2.
Так как точки отсортированы в лексикографическом порядке, то возможен бинарный поиск (дихотомия). Т. е. сложность алгоритма ~  , где N – количество точек на уровне.
Шаг 4: Заносим точки pi, pr и pj в соответствующие структуры и переобозначим pi = pr.
Шаг 5: Повторяем шаг 3-4 до тех пор пока pi не совпадет с pj.
Шаг 6: Если в построенной нами выпуклой оболочки встречаются вогнутые сегменты то соединяем крайние точки таких сегментов (Рис. 11.3).
Рис. 11.3. Преобразование выпуклой оболочки.
|
