Как построить список двусвязных ребер с учетом набора отрезков?

10

Для данного плоского графа встроены в плоскости, определяется набором отрезков Е = { е 1 , . , , , e m } , каждый сегмент e i представлен своими конечными точками { L i , R i } . Создайте структуру данных DCEL для плоского подразделения, опишите алгоритм, докажите его правильность и покажите сложность.г(В,Е)Езнак равно{е1,,,,,ем}ея{Lя,ря}

В соответствии с этим описанием структуры данных DCEL существует множество соединений между различными объектами (то есть вершинами, ребрами и гранями) DCEL. Таким образом, DCEL, похоже, сложно построить и поддерживать.

Знаете ли вы какой-либо эффективный алгоритм, который можно использовать для построения структуры данных DCEL?

ком
источник

Ответы:

8

Структура данных (соглашения соответствуют статье в Википедии ):

struct half_edge;

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
};

struct face {
    struct half_edge *rep;  /* rep->left == this */
};

struct half_edge {
    struct half_edge *prev;  /* prev->next == this */
    struct half_edge *next;  /* next->prev == this */
    struct half_edge *twin;  /* twin->twin == this */
    struct vertex *tail;     /* twin->next->tail == tail &&
                                prev->twin->tail == tail */
    struct face *left;       /* prev->left == left && next->left == left */
};

Алгоритм

  1. Для каждой конечной точки создайте вершину .

  2. Для каждого входного сегмента создайте два пол ребра и назначьте их хвостовые вершины и двойники.

  3. Для каждой конечной точки сортируйте половинки, хвостовая вершина которых является этой конечной точкой, по часовой стрелке.

  4. Для каждой пары половин e1, e2по часовой стрелке присвойте e1->twin->next = e2и e2->prev = e1->twin.

  5. Выберите один из пол ребер и назначьте его в качестве представителя для конечной точки. (Вырожденный регистр: если eв отсортированном списке есть только одна половина , set e->twin->next = eи e->prev = e->twin). Следующие указатели - перестановка на пол ребер.

  6. Для каждого цикла выделите и назначьте структуру лица .

PSHUFB
источник
2
В основном куча скучного бухгалтерии. Вероятно, поэтому авторы учебников не хотят вдаваться в подробности.
pshufb