202
правки
Изменения
Нет описания правки
[[Файл:DCEL3.png|200px|thumb|right|(а) РСДС, (б) входы по вершинам head_V [1..n] и (в) входы по граням head_F[1..l]]]
'''ППЛГ''' {{---}} Плоский прямолинейный планарный граф.
'''РСДС''' {{---}} Реберный список с двойными связями.
==РСДС==
===Первое Формальное описание===
Реберный список с двойными связями особенно удобен для представления ППЛГ.
Пусть задан граф <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, half-edge, face'':*''Vertex'' {{--- }} это точка сочленения. Содержит координаты точки. А так же также указатель на инцидентное ребро.*''Face'' {{-- -}} содержит указатель на наружную компоненту (некоторое ребро на его границе). Для неограниченных поверхностей это nil. Так же содержит внутреннюю компонентусписок указателей на внутренние компоненты (дырки), которая то есть указатель , по указателю на некое ребро, с которого можно начать описывать внутреннюю область одно из инцидентных каждой дырке рёбер (опять жеnil, может быть nilесли дырок нет).*''Half-edge'' {{--- }} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
<pre>
struct vertex {
<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> У нас есть множество прямых. Мы хотим представить это множество в виде РСДС. Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритмбудет такой:Для каждой конечной точки создаем vertex. Для каждого входного сегмента создаем 2 * Локализовать рандомную точку прямой в face* Найти half-edge 'и присваиваем vertex , которые пересекает эта прямая(их будет не больше 2, если считать пересечение в origin точке за одно ребро)* Разбить текущий face на два face1 и face2** Если пересечение не в точке, разбиваем ребра на два {{---}} a, b и создаем поля twin. Для каждой конечной точки сортируем (по часовой стрелке) c, d, так как пересечения два** Создаем два half-edge{{---}} отрезок прямой, попадающий в фэйс** Перекидываем ссылки этих half-edgeй как надо** Не забываем поменять у которых origin vertex half-edgeй исходного face поле incident_face на face1 и есть эта точка. Для каждой пары halfface2 соответственно* Мы знаем куда(в какие фэйсы {{---}} edge e1, e2, по часовой стрелке присваиваем e1->twin->next incident_face) пошла наша прямая. Запускаемся от них и разбиваем их аналогично. Если пересечение было в точке, перебираем faceы(next_face = e2 и e2edge->prev = e1->twin->incident_face), пока не найдем нужный. Выбираем один из этих halfЕсли фэйс бесконечный {{---edge и делаем его представителем точки. (Вырожденный случай}} идем только в одну сторону Вот эти ссылки надо не забыть поменять: если есть только 1 half<pre>half_edge1->origin = A;half_edge2->origin = B; half_edge1-edge в отсортированном списке, то присваиваем e>twin = half_edge2;half_edge2->twin= half_edge1;half_edge1->incident_face = face1;half_edge2->incident_face = face2; half_edge1->next = e и eb;b->prev = half_edge1;half_edge1->prev = d;d->next = half_edge1; half_edge2->next = c;c->prev = half_edge2;half_edge2->prev = ea;a->twinnext = half_edge2;</pre> ==См. Если сделать четко, то это не понадобится)также==[http://cs. Следующие указатели это перестановки half-edgestackexchange. В каждом цикле находим и создаем facecom/a/18167 Источник.] [[Категория:Алгоритмы]][[Категория:Теория графов]][[Категория:Вычислительная геометрия]]
