j = 0;
p -> add Vertex ( s [i], j -1 );
}
return p;
}

Несложно заметить, что временные затраты данного алгоритма составляют 0(п2).

8.8. Построение выпуклой оболочки Пусть S - конечный набор точек на плоскости. Выпуклой оболочкой convS набора S называется пересечение всех выпуклых многоугольников, содержащих S. Ясно, что convS - это выпуклый многоугольник, все вершины которого содержатся в S (заметим, что не все точки из S являются вершинами выпуклой оболочки).

Один из способов построения выпуклой оболочки конечного набора точек S на плоскости напоминает вычерчивание при помощи карандаша и линейки. Вначале выбирается точка а е S, заведомо являющаяся вершиной границы выпуклой оболочки. В качестве такой точки можно взять самую левую точку из набора S (если таких точек несколько, выбираем самую нижнюю). Затем вертикальный луч поворачивается вокруг этой ючки по направлению часовой стрелки до тех пор, пока не на8. Основные алгоритмы вычислительной геометрии ткнется на точку b е S. Тогда отрезок ah будет ребром границы выпуклой оболочки. Для поиска следующего ребра будем продолжать вращение луча по часовой стрелке; на этот раз вокруг точки b до встречи со следующей точкой с е S. Отрезок be будет следующим ребром границы выпуклой оболочки. Процесс повторяется до тех пор, пока мы снова не вернемся в точку а. Этот метод называется методом "заворачивания подарка".

Основным шагом алгоритма является отыскание точки, следующей за точкой, вокруг которой вращается луч.

Следующая процедура реализует описанный алгоритм. Входной массив s должен иметь длину п + 1, где п - количество входных точек, поскольку в конец массива процедура записывает ограничивающий элемент ^[0].

(21 // File giftwrap.cpp #include "polygon.h"
template <class T> void swap ( T a, T b ) f

Тег с = a; a = b; b = a;

}
Polygon * giftWrapHull ( Vector2D s 0, int n ) {
int a = 0;
// find leftmost point for (int i = 1; i < n; i++ ) if ( s [i].x < s [a].x )
a = i; s [n] = s [a];
Polygon * p = new Polygon; for (i = 0; i < n; i++ )

⇐ Предыдущая| |Следующая ⇒