Поиск по сайту.

Другие алгоритмы.

Математика:
Вычислительная геометрия:
Построение выпуклой оболочки.



Gift Wrapping.

Автор: Unknown.
Перевод: Кантор И.

     Этот алгоритм обводит точки линией, как будто это - кусок веревки. На рисунке ниже дана подробная иллюстрация его действия.

Псевдокод.

     Находим нижнюю-правую точку. Пусть это - i(0). i=i(0).
     Повторять :
           - Для каждого j != i вычисляем точку с наименьшим углом от предыдущей стороны ( для второй точки - от горизонтали ). Если есть две таких - берем ту, до которой расстояние больше. Пусть ее номер - k.
           - Выводим сторону из точек с номерами i и k. i = k.
     пока i не станет равно i(0).




Вверх по странице, к оглавлению и навигации.