 |
Другие алгоритмы.
Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.
Алгоритм Мелькмана.
Автор: Unknown.
Перевод: Кантор И.
Что интересно, точки могут поступать по мере выполнения алгоритма, и их количество может быть заранее не известно. Главное, чтобы ломаная не пересекалась.
Для начала объявим вспомогательную функцию, которая для любой тройки x, y, z будет f>0, f=0 или f<0 в зависимости от того, находится ли z справа, на одной линии или слева от линии (x, y).
Пусть ломаная задана точками v1, ..., vm.
Алгоритм начинает с пустого дека D. (Дек - вид списка)
Операции:
push v - положить элемент на верх дека,
insert v - положить элемент под низ дека,
pop - убрать верхний элемент дека,
remove - удалить нижний элемент дека.
Псевдокод.
Шаг 1:Ввод v1, v2, v3;
if (v1,v2,v3)>0
then {push v1; push v2;}
else {push v2; push v1;}
push v3; insert v3;
Шаг 2:
Ввод v;
until ((v,db,db+1)<0 or (dt-1,dt,c)<0) do { ввод v };
Шаг 3:
until ((dt-1,dt,v)>0) do pop;
push v;
Шаг 4:
until ((v,db,db+1)>0) do remove;
insert v;
Идти на Шаг 2.
Реализация на Си
Вверх по странице, к оглавлению и навигации.