202
правки
Изменения
Нет описания правки
==РСДС==
===Первое Формальное описание===
Реберный список с двойными связями особенно удобен для представления ППЛГ.
Пусть задан граф <tex>G = (V, E)</tex>, <tex>V = \{v_1, v_2... v_n\}</tex>, а <tex>E = \{e_1, e_2... e_n\}</tex>. Главная компонента РСДС для планарного графа это ''реберный узел''. Между ребрами графа и реберными узлами РСДС существует взаимно однозначное соответствие, т.е. каждое ребро представлено в РСДС ровно один раз. Реберный узел РСДС, соответствующий ребру графа, например, <tex>e_k = \{v_1, v_2\} </tex> имеет 4 поля (<tex>V1, V2, F1, F2</tex>) и 2 указателя (<tex>P1, P2</tex>). Поле <tex>V1</tex> содержит начало ребра, а поле <tex>V2</tex> содержит его конец (так изначально неориентированное ребро получает условную ориентацию). Поля <tex>F1</tex> и <tex>F2</tex> содержат имена граней, лежащих слева и справа от ориентированного ребра (<tex>v_1, v_2</tex>). Указатель <tex>P1</tex> (соответственно <tex>P2</tex>) задает реберный узел, содержащий первое ребро, встречаемое вслед за ребром (<tex>v_1, v_2</tex>), при повороте от него против часовой стрелки вокруг <tex>v_1</tex> (соответственно <tex>v_2</tex>).
[[Файл:DCEL4.png|300px|thumb|right|Ко второму описанию]]
===Второе Неформальное описание===
РСДС состоит из 3 компонент:
*''Vertex'' {{---}} это точка сочленения. Содержит координаты точки. А также указатель на инцидентное ребро.
*''Face'' {{---}} содержит указатель на наружную компоненту (некоторое ребро на его границе). Для неограниченных поверхностей это nil. Так же содержит внутреннюю компонентусписок указателей на внутренние компоненты (дырки), которая то есть указатель , по указателю на некое ребро, с которого можно начать описывать внутреннюю область одно из инцидентных каждой дырке рёбер (опять жеnil, может быть nilесли дырок нет).
*''Half-edge'' {{---}} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
<pre>
<pre>
struct face {
};
</pre>
==Построение РСДС множества прямых==
{|align="right"|-valign="top"|[[Файл:before.png|400px200px|thumb|leftright|былоБыло]]|[[Файл:next.png|400px|thumb|right|Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face]]|}<b>Этот раздел читать довольно бесполезно, нужно переписать сюда соответствующую главу из де Берга.</b>
У нас есть множество прямых. Мы хотим представить это множество в виде РСДС.
Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:
* Локализовать рандомную точку прямой в face
* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать пересечение в точке за одно ребро)
d->next = half_edge1;
half_edge2->next = ac;ac->prev = half_edge2;half_edge2->prev = ca;ca->next = half_edge2;
</pre>
==См. также==
[http://cs.stackexchange.com/a/18167 Более поясняющая статьяИсточник.] [[Категория:Алгоритмы]][[Категория:Теория графов]][[Категория:Вычислительная геометрия]]
