Теоретические оценки сложности.
Полигоны LиRсливаются за время, пропорциональное |L| + |R|.Чтобы найти каждый мостик, функцияbridgeпопеременно проверяет каждую вершину в полигонахLиR.Если вершина просмотрена, то снова к ней не возвращаются. Следовательно, каждый из двух мостиков находится за время О(|L| + |R|), так что оба обращения из функцииmergeк функцииbridgeзанимают линейное время. Более того, функцияmergeзатрачивает линейное время на обращение к функцииleastVertexи постоянное время на свои другие операции. Это означает, что функцияmergeвыполняется за линейное время.
Из сказанного следует, что обращение на верхнем уровне к функции mHullвыполняется за времяТ(п),где
В результате получаем решение
.
На параметры алгоритма не влияет начальная сортировка точек, поскольку она также занимает время O(nlogп).Следовательно, в худшем случае программа слияния оболочек выполняется за времяO(nlogп).
Структуры данных
Класс “Point”: содержит элементы данных х и у для хранения координат точки. Компонентные функции обеспечивают выполнение операций по определению положения точки относительно заданного отрезка прямой линии и вычисления расстояния от заданной точки до прямой линии.
class Tpoint : public TGeometryObj
{
private:
protected:
public:
double x;
double y;
Tpoint(double _x = 0.0, double _y = 0.0);
int classify(Tpoint & p0, Tpoint & p1);
Tpoint operator+(Tpoint& p);
Tpoint operator-(Tpoint& p);
friend Tpoint operator*(double s, Tpoint& p);
double operator[](int i);
int operator==(Tpoint& p);
int operator!=(Tpoint& p);
int operator<(Tpoint& p);
int operator>(Tpoint& p);
double length(void);
TTwoCoord* GetCoords(int &n);
int GetType(void);
};
Tpoint operator*(double s, Tpoint& p);
Класс «Node»: объекты данного класса являются узлами в связанных списках, которые используются для представления точек.
class Node
{
private:
protected:
Node* _next;
Node* _prev;
public:
Node*insert(Node*);
/*объединение двух узлов*/
void splice(Node*);
Node* remove(void);
virtual ~Node(void);
Node(void);
};
Класс «Vertex»: реализует хранение виде циклического списка с двойными связями полигона, который рассматривается в виде кольца вершин. Т.к. вершины полигона существуют одновременно как точки на плоскости и узлы в связанном списке, поэтому класс Vertex формируется на основе класса Point и Node. От Point он наследует х и у, а от Node указатели на следующую и предыдущую вершины относительно текущей.
class Vertex : public Tpoint , public Node
{
private:
protected:
public:
Vertex(Tpoint p);
Vertex* insert(Vertex*);
Vertex* split(Vertex* b);
Vertex* ccw(void); - указатель на предшественника
Tpointpoint(void);- возвращает точку на плоскости, в которой находится вершина
voidsplice(Vertex*b);
Vertex*cw(void);- указатель на последователя
Vertex* remove(void);
Vertex* neighbor(int rotation);
intGetType(void);
};
Класс «Polygon»: содержит элемент данных, указывающий на некоторую вершину в связном списке, представляющем полигон.
class Tpolygon : public TGeometryObj
{
private:
Vertex* _v;
int _size;
protected:
public:
Vertex* setV(Vertex* v);
Vertex* insert(Tpoint& p);
Tpolygon* split(Vertex* b);
void resize(void);
Tpolygon(Vertex*);
~Tpolygon(void);
Tpolygon(void);
Vertex* v(void);
Vertex* neighbor(int rotation);
Vertex* advance(int rotation);
int size(void);
Tpoint point(void);
Tpolygon(Tpolygon& p);
TTwoCoord* GetCoords(int& n);
int GetType(void);
Vertex* cw(void);
};