170
правок
Изменения
м
Нет описания правки
===Второе описание===
РСДС состоит из 3 компонент:
*''Vertex'' {{---}} это точка сочленения. Содержит координаты точки. А так же также указатель на инцидентное ребро.
*''Face'' {{---}} содержит указатель на наружную компоненту (некоторое ребро на его границе). Для неограниченных поверхностей это nil. Так же содержит внутреннюю компоненту, которая есть указатель на некое ребро, с которого можно начать описывать внутреннюю область (опять же, может быть nil).
*''Half-edge'' {{---}} это ребро. Содержит указатели на точку, откуда исходит (origin), указатель на ребро близнец (twin)(направленное в другую сторону), инцидентную поверхность (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. [http://cs.stackexchange.com/a/2516]
