Структуры данных.

Для имитации береговой линии используется бинарное дерево. Узлами дерева являются брекпоинты, листьями дерева являются арки. Арка содержит фокус параболы. Брекпоинт не содержит никакой информации. Он нужен лишь для того, что бы указать сам факт пересечения арок.

<Рисунок пример дерева>

Для удобства, все три структуры (арка, брекпоинт, ендпоинт) унаследованы от базового класса, который хранит идентификатор, являющийся типом элемента. По данному идентификатору мы сможем узнать, чем является элемент, аркой, брекпоинтом или ендпоинтом.

struct IElement

{

enum ElementType

{

ARC,

BREAK_POINT,

END_POINT,

};

const ElementType type;

};

struct ArcElement : public IElement;

struct BPElement : public IElement;

struct EPElement : public IElement;

Во время работы алгоритма у нас будут появляться грани, поэтому нам нужен список граней. Грань содержит две точки на концах, при этом, когда возникает новая грань, мы не знаем координаты этих точек. Мы лишь знаем, что на концах грани есть брекпоинты, когда три грани пересекаются, в точке пересечения брекпоинты превращаются в ендпоинты. Таким образом грань может быть ограничена двумя брекпоинтами, брекпоинтом и ендпоинтом или двумя ендпоинтами. Так же грань содержит две точки, между которыми она расположена.

struct EdgeElement

{

IElement *p1;

IElement *p2;

ArcElement *site1;

ArcElement *site2;

}

Список граней:

std::vector<EdgeElement *> mListEdgeElement;

Список граней у нас является списком указателей на грани, т.к. нам потребуется в дальнейшем ссылаться на грани в разных местах.

Можно было заметить, что во время работы алгоритма у нас появляются и удаляются брекпоинты и ендпоинты (только появляются), по которым строятся грани. Поэтому нам нужен список, в котором будут храниться все существующие брекпоинты и ендпоинты.

std::vector<IElement *> mListPoints;

Формат входных и выходных данных:

В первой реализации алгоритма я еще не думал о формате входных и выходных данных, на вход я подавал список точек, что вполне очевидно, а на выходе получал список полигонов в формате

std::map<glm::vec2, std::set<glm::vec2>> mPoligons;

Где ключ в std::map - точка, а значение - список вершин, упорядоченных против часовой стрелки.

Однако данный формат был не удобный и не эффективный по памяти, поэтому я пришел к следующему формату.

Входные данные:

std::vector<glm::vec2> mListSites; // Список точек

Выходные данные:

std::vector<glm::vec2> mListVertex; // Список вершин

Грань. Содержит два индекса на точки из списка точек (грань лежит между этими двумя точками) и два индекса на вершины из списка вершин (вершины являются концами отрезка грани).

<рисунок грани>

struct Edge

{

unsigned int site1;

unsigned int site2;

unsigned int vertex1;

unsigned int vertex2;

}

std::vector<Edge> mListEdge; // Список граней

Данный список граней отличается от вышеприведенного списка граней (mListEdgeElement), оба списка нужны. Первый список (mListEdgeElement) используется в ходе выполнения алгоритма. В него добавляются новые грани, концы которых нам не известны. Когда мы находим ендпоинты, как уже отмечалось, брекпоинты в гранях заменяются на ендпоинты. Если после обновления граней у нас появилась грань, содержащая два ендпоинта, т.е. мы узнали точные границы грани, мы удаляем грань из этого списка и добавляем данную грань в список mListEdge. Таким образом, в списке выходных граней у нас содержутся грани с известными границами.