222
правки
Изменения
м
→Построение РСДС множества прямых
==Построение РСДС множества прямых==
{|align="right"|-valign="top"|[[Файл:before.png|200px|thumb|right|Было]]|[[Файл:next.png|400px|thumb|right|Добавляем жирную прямую. [a+b] это ребро, которое было в начальном face]]|}
У нас есть множество прямых. Мы хотим представить это множество в виде РСДС.
Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой:
* Локализовать рандомную точку прямой в face
* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать пересечение в точке за одно ребро)
d->next = half_edge1;
half_edge2->next = ac;ac->prev = half_edge2;half_edge2->prev = ca;ca->next = half_edge2;
</pre>
==См. также==
[http://cs.stackexchange.com/a/18167 Более поясняющая статья.]
