Перевод: Кантор И. e-mail: algolist@mail.ru web: iliakan@gmail.com
Этот алгоритм обводит точки линией, 'заворачивая' в выпуклую оболочку. На рисунке ниже дана подробная иллюстрация его действия.
Находим нижнюю-правую точку. Пусть это - i(0). i=i(0).
Повторять :
- Для каждого j != i вычисляем точку с наименьшим
углом от предыдущей стороны
( для второй точки - от горизонтали ).
Если есть две таких - берем ту,
до которой расстояние больше. Пусть ее номер - k.
- Выводим сторону из точек с номерами i и k. i = k.
пока i не станет равно i(0).
Исходник собственно функции - simple_convex() в geom.c. Программа компилируется и работает под GCC 2.95. Скачатьzip.
|