Изменения

Алгоритм:Для каждой конечной точки создаем 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]

Будем добавлять прямые по одной. Изначально у нас есть фэйс, который представляет собой всю плоскость. Алгоритм будет такой: * Локализовать рандомную точку прямой в face* Найти half-edge'и, которые пересекает эта прямая(их будет не больше 2, если считать что пересечение в точке за одно ребро)* Разбить текущий face на два face1 и face2** Если пересечение не в точке, разбиваем ребра на два {{---}} a, b и c, d, так как пересечения два** Создаем два half-edge {{---}} отрезок прямой, попадающий в фэйс** <pre>half_edge1->origin = intersection_line_and_edge1;half_edge2->origin = intersection_line_and_edge2; half_edge1->twin = half_edge2;half_edge2->twin = half_edge1;half_edge1->incident_face = face1;half_edge2->incident_face = face2; half_edge1->next = a;a->prev = half_edge1;half_edge1->prev = c;c->next = half_edge1; half_edge2->next = b;b->prev = half_edge2;half_edge2->prev = d;d->next = half_edge2;</pre>** Не забываем поменять у half-edgeй исходного face поле incident_face на face1 и face2 соответственно* Мы знаем куда(в какие фэйсы {{---}} edge->twin->incident_face) пошла наша прямая. Запускаемся от них и разбиваем их аналогично. Если пересечение было в точке, перебираем faceы(next_face = edge->prev->twin->incident_face), пока не найдем нужный. Если фэйс бесконечный {{---}} идем только в одну сторону  ==См. также==[http://cs.stackexchange.com/a/18167 Более поясняющая статья.] К сожалению нет времени перевести, но там и так все достаточно понятно.