ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: « 400px|thumb|incident_face|Представление плоского графа с помощью РСДС [[Файл:DCEL2.png|200px|thum...»)
 
(не показана 21 промежуточная версия 7 участников)
Строка 1: Строка 1:
  
[[Файл:DCEL.png|400px|thumb|incident_face|Представление плоского графа с помощью РСДС]]
+
[[Файл:DCEL.png|400px|thumb|left|Представление плоского графа с помощью РСДС]]
 
[[Файл:DCEL2.png|200px|thumb|right|Плоский граф, ребрам которого придана произвольная ориентация для представления его с помощью РСДС. Стрелки вокруг вершин соответствуют указателям (P1, P2)]]
 
[[Файл:DCEL2.png|200px|thumb|right|Плоский граф, ребрам которого придана произвольная ориентация для представления его с помощью РСДС. Стрелки вокруг вершин соответствуют указателям (P1, P2)]]
 
[[Файл:DCEL3.png|200px|thumb|right|(а) РСДС, (б) входы по вершинам head_V [1..n] и (в) входы по граням head_F[1..l]]]
 
[[Файл: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</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>).
 
Пусть задан граф <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|Ко второму описанию]]
 
[[Файл:DCEL4.png|300px|thumb|right|Ко второму описанию]]
===Второе описание===
+
===Неформальное описание===
РСДС состоит из 3 компонент.
+
РСДС состоит из 3 компонент:
''Vertex, half-edge, face''
+
*''Vertex'' {{---}} это точка сочленения. Содержит координаты точки. А также указатель на инцидентное ребро.
''Vertex'' - это точка сочленения. Содержит координаты точки. А так же указатель на инцидентное ребро.
+
*''Face'' {{---}} содержит указатель на некоторое ребро на его границе. Для неограниченных поверхностей это nil. Так же содержит список указателей на внутренние компоненты (дырки), то есть, по указателю на одно из инцидентных каждой дырке рёбер (nil, если дырок нет).
''Face'' - содержит указатель на наружную компоненту (некоторое ребро на его границе). Для неограниченных поверхностей это nil. Так же содержит внутреннюю компоненту, которая есть указатель на некое ребро, с которого можно начать описывать внутреннюю область (опять же, может быть nil).
+
*''Half-edge'' {{---}} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
''Half-edge'' - это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
 
 
<pre>
 
<pre>
 
struct vertex {
 
struct vertex {
Строка 31: Строка 30:
 
<pre>
 
<pre>
 
struct face {
 
struct face {
     outer_component *out;
+
     half_edge *out;
     inner_component *in;
+
     list<half_edge*> in;  
 
};
 
};
 
</pre>
 
</pre>
 
<pre>
 
<pre>
 
struct half_edge {
 
struct half_edge {
     half_edge *prev; /* prev->next == this */
+
     half_edge *prev;     /* prev->next == this */
     half_edge *next; /* next->prev == this */
+
     half_edge *next;     /* next->prev == this */
     half_edge *twin; /* twin->twin == this */
+
     half_edge *twin;     /* twin->twin == this */
     vertex *origin;     /* twin->next->origin == origin &&
+
     vertex *origin;     /* twin->next->origin == origin &&
                                prev->twin->origin == origin */
+
                            prev->twin->origin == origin */
     face *incident_face;       /* prev->incident_face == incident_face && next->incident_face == incident_face */
+
     face *incident_face; /* prev->incident_face == incident_face &&  
 +
                            next->incident_face == incident_face */
 
};
 
};
 
</pre>
 
</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.
+
{|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 Источник.]
 +
 
 +
[[Категория:Алгоритмы]]
 +
[[Категория:Теория графов]]
 +
[[Категория:Вычислительная геометрия]]

Версия 14:51, 14 ноября 2018

Представление плоского графа с помощью РСДС
Плоский граф, ребрам которого придана произвольная ориентация для представления его с помощью РСДС. Стрелки вокруг вершин соответствуют указателям (P1, P2)
(а) РСДС, (б) входы по вершинам head_V [1..n] и (в) входы по граням head_F[1..l]

ППЛГ — Плоский прямолинейный граф.

РСДС — Реберный список с двойными связями.

ППЛГ

Планарный граф, уложенный на плоскости, принято называть плоским. Плоская укладка планарного графа [math]G = (V, E)[/math] — это отображение каждой вершины из [math]V[/math] в точку на плоскости, а каждого ребра из [math]E[/math] в простую линию, соединяющую пару образов концевых вершин этого ребра так, чтобы образы ребер пересекались только в своих концевых точках. Хорошо известно, что любой планарный граф можно уложить на плоскости так, чтобы все ребра отобразились в прямолинейные отрезки.

РСДС

Формальное описание

Реберный список с двойными связями особенно удобен для представления ППЛГ. Пусть задан граф [math]G = (V, E)[/math], [math]V = \{v_1, v_2... v_n\}[/math], а [math]E = \{e_1, e_2... e_n\}[/math]. Главная компонента РСДС для планарного графа это реберный узел. Между ребрами графа и реберными узлами РСДС существует взаимно однозначное соответствие, т.е. каждое ребро представлено в РСДС ровно один раз. Реберный узел РСДС, соответствующий ребру графа, например, [math]e_k = \{v_1, v_2\} [/math] имеет 4 поля ([math]V1, V2, F1, F2[/math]) и 2 указателя ([math]P1, P2[/math]). Поле [math]V1[/math] содержит начало ребра, а поле [math]V2[/math] содержит его конец (так изначально неориентированное ребро получает условную ориентацию). Поля [math]F1[/math] и [math]F2[/math] содержат имена граней, лежащих слева и справа от ориентированного ребра ([math]v_1, v_2[/math]). Указатель [math]P1[/math] (соответственно [math]P2[/math]) задает реберный узел, содержащий первое ребро, встречаемое вслед за ребром ([math]v_1, v_2[/math]), при повороте от него против часовой стрелки вокруг [math]v_1[/math] (соответственно [math]v_2[/math]).

Ко второму описанию

Неформальное описание

РСДС состоит из 3 компонент:

  • Vertex — это точка сочленения. Содержит координаты точки. А также указатель на инцидентное ребро.
  • Face — содержит указатель на некоторое ребро на его границе. Для неограниченных поверхностей это nil. Так же содержит список указателей на внутренние компоненты (дырки), то есть, по указателю на одно из инцидентных каждой дырке рёбер (nil, если дырок нет).
  • Half-edge — это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
struct vertex {
    x, y;
    half_edge *rep;  /* rep->origin == this */
};
struct face {
    half_edge *out;
    list<half_edge*> in; 
};
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 */
};

Построение РСДС множества прямых

Было
Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face

Этот раздел читать довольно бесполезно, нужно переписать сюда соответствующую главу из де Берга.

У нас есть множество прямых. Мы хотим представить это множество в виде РСДС.

Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:

  • Локализовать рандомную точку прямой в 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), пока не найдем нужный. Если фэйс бесконечный — идем только в одну сторону

Вот эти ссылки надо не забыть поменять:

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;

См. также

Источник.