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>
<pre>
struct half_edge {
half_edge *prev; /* prev->next == this */ half_edge *next; /* next->prev == this */ half_edge *twin; /* twin->twin == this */ vertex *origin; /* twin->next->origin == origin && prev->twin->origin == origin */ face *incident_face; /* prev->incident_face == incident_face && next->incident_face == incident_face */
};
</pre>
==Построение РСДС множества прямых==
{|align="right"
|-valign="top"
|[[Файл:before.png|200px|thumb|right|Было]]
|[[Файл:next.png|400px|thumb|right|Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face]]
|}
<b>Этот раздел читать довольно бесполезно, нужно переписать сюда соответствующую главу из де Берга.</b>
Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:* Локализовать рандомную точку прямой в face* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать пересечение в точке за одно ребро)* Разбить текущий face на два face1 и face2** Если пересечение не в точке, разбиваем ребра на два {{---}} a, b и c, d, так как пересечения два** Создаем два half-edge {{---}} отрезок прямой, попадающий в фэйс** Перекидываем ссылки этих half-edgeй как надо** Не забываем поменять у half-edgeй исходного face поле incident_face на face1 и face2 соответственно* Мы знаем куда(в какие фэйсы {{---}} edge->twin->incident_face) пошла наша прямая. Запускаемся от них и разбиваем их аналогично. Если пересечение было в точке, перебираем faceы(next_face = edge->prev->twin->incident_face), пока не найдем нужный. Если фэйс бесконечный {{---}} идем только в одну сторону Вот эти ссылки надо не забыть поменять:<pre>half_edge1->origin = A;half_edge2->origin = B; half_edge1->twin = half_edge2;half_edge2->twin = half_edge1;half_edge1->incident_face = face1;half_edge2->incident_face = face2; half_edge1->next = b;b->prev = half_edge1;half_edge1->prev = d;d->next = half_edge1; half_edge2->next = c;c->prev = half_edge2;half_edge2->prev = a;a->next = half_edge2;</pre> ==См. также==[http://cs.stackexchange.com/a/18167 Более поясняющая статьяИсточник.] К сожалению нет времени перевести, но там и так все достаточно понятно. [[Категория:Алгоритмы]][[Категория:Теория графов]][[Категория:Вычислительная геометрия]]
