139
правок
Изменения
Новая страница: « 400px|thumb|incident_face|Представление плоского графа с помощью РСДС [[Файл:DCEL2.png|200px|thum...»
[[Файл:DCEL.png|400px|thumb|incident_face|Представление плоского графа с помощью РСДС]]
[[Файл:DCEL2.png|200px|thumb|right|Плоский граф, ребрам которого придана произвольная ориентация для представления его с помощью РСДС. Стрелки вокруг вершин соответствуют указателям (P1, P2)]]
[[Файл:DCEL3.png|200px|thumb|right|(а) РСДС, (б) входы по вершинам head_V [1..n] и (в) входы по граням head_F[1..l]]]
'''ППЛГ''' --- Плоский прямолинейный планарный граф.
'''РСДС''' --- Реберный список с двойными связями.
==ППЛГ==
[[Укладка графа на плоскости|Планарный граф]], уложенный на плоскости, принято называть ''плоским''.
'''Плоская укладка планарного графа''' <tex>G = (V, E)</tex> --- это отображение каждой вершины из <tex>V</tex> в точку на плоскости, а каждого ребра из <tex>E</tex> в простую линию, соединяющую пару образов концевых вершин этого ребра так, чтобы образы ребер пересекались только в своих концевых точках. Хорошо известно, что любой планарный граф можно уложить на плоскости так, чтобы все ребра отобразились в прямолинейные отрезки.
==РСДС==
===Первое описание===
Реберный список с двойными связями особенно удобен для представления ППЛГ.
Пусть задан граф <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).
''Half-edge'' - это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
<pre>
struct vertex {
x, y;
half_edge *rep; /* rep->origin == this */
};
</pre>
<pre>
struct face {
outer_component *out;
inner_component *in;
};
</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>
==Построение РСДС множетсва прямых==
Алгоритм:
Для каждой конечной точки создаем vertex. Для каждого входного сегмента создаем 2 half-edge и присваиваем vertex в origin и создаем поля twin. Для каждой конечной точки сортируем (по часовой стрелке) half-edge, у которых origin vertex и есть эта точка. Для каждой пары half-edge e1, e2, по часовой стрелке присваиваем e1->twin->next = e2 и e2->prev = e1->twin. Выбираем один из этих half-edge и делаем его представителем точки. (Вырожденный случай: если есть только 1 half-edge в отсортированном списке, то присваиваем e->twin->next = e и e->prev = e->twin. Если сделать четко, то это не понадобится). Следующие указатели это перестановки half-edge. В каждом цикле находим и создаем face.
