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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 13: Строка 13:
  
 
==РСДС==
 
==РСДС==
===Формальное описание===
+
===Первое описание===
 
Реберный список с двойными связями особенно удобен для представления ППЛГ.
 
Реберный список с двойными связями особенно удобен для представления ППЛГ.
 
Пусть задан граф <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'' {{---}} это точка сочленения. Содержит координаты точки. А также указатель на инцидентное ребро.
 
*''Vertex'' {{---}} это точка сочленения. Содержит координаты точки. А также указатель на инцидентное ребро.
*''Face'' {{---}} содержит указатель на некоторое ребро на его границе. Для неограниченных поверхностей это nil. Так же содержит список указателей на внутренние компоненты (дырки), то есть, по указателю на одно из инцидентных каждой дырке рёбер (nil, если дырок нет).
+
*''Face'' {{---}} содержит указатель на наружную компоненту (некоторое ребро на его границе). Для неограниченных поверхностей это nil. Так же содержит внутреннюю компоненту, которая есть указатель на некое ребро, с которого можно начать описывать внутреннюю область (опять же, может быть nil).
 
*''Half-edge'' {{---}} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
 
*''Half-edge'' {{---}} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (incident_face), и указатели на следующее и предыдущие ребра.
 
<pre>
 
<pre>
Строка 30: Строка 30:
 
<pre>
 
<pre>
 
struct face {
 
struct face {
     half_edge *out;
+
     outer_component *out;
     list<half_edge*> in;  
+
     inner_components *in; (список какой-нибудь)
 
};
 
};
 
</pre>
 
</pre>
Строка 47: Строка 47:
  
 
==Построение РСДС множества прямых==
 
==Построение РСДС множества прямых==
{|align="right"
+
[[Файл:before.png|400px|thumb|left|было]]
|-valign="top"
+
[[Файл:next.png|400px|thumb|right|Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face]]
|[[Файл:before.png|200px|thumb|right|Было]]
 
|[[Файл:next.png|400px|thumb|right|Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face]]
 
|}
 
<b>Этот раздел читать довольно бесполезно, нужно переписать сюда соответствующую главу из де Берга.</b>
 
  
 
У нас есть множество прямых. Мы хотим представить это множество в виде РСДС.
 
У нас есть множество прямых. Мы хотим представить это множество в виде РСДС.
  
 
Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:
 
Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:
 +
 
* Локализовать рандомную точку прямой в face
 
* Локализовать рандомную точку прямой в face
 
* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать пересечение в точке за одно ребро)
 
* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать пересечение в точке за одно ребро)
Строка 81: Строка 78:
 
d->next = half_edge1;
 
d->next = half_edge1;
  
half_edge2->next = c;
+
half_edge2->next = a;
c->prev = half_edge2;
+
a->prev = half_edge2;
half_edge2->prev = a;
+
half_edge2->prev = c;
a->next = half_edge2;
+
c->next = half_edge2;
 
</pre>
 
</pre>
  
 
==См. также==
 
==См. также==
[http://cs.stackexchange.com/a/18167 Источник.]
+
[http://cs.stackexchange.com/a/18167 Более поясняющая статья.]
 
 
[[Категория:Алгоритмы]]
 
[[Категория:Теория графов]]
 
[[Категория:Вычислительная геометрия]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: