Я узнал об этом в университете, но это было недавно.
В ответ на этот вопрос я также искал в Интернете какую-либо хорошую документацию, но не нашел ни одной хорошей, но мы можем просмотреть краткий пример порядка и вставки / удаления CCW и CW.Посмотрите на эту таблицу и графику: 
с этой страницы:
http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/model/winged-e.html
Таблица дает только запись для одного ребра a, в реальной таблице, которую вы имеетеэтот ряд для каждого края.Вы можете видеть:
- левый предшественник,
- левый преемник,
- правый предшественник,
- правый преемник
но здесь наступает критическая точка: она дает их относительно направления края, который в данном случае равен X->Y, и когда он проходит вправо (e->a->c).
Так что для CW-порядка прохождения графа это очень легко прочитать: у ребра a left есть правый преемник c, а затем вы смотрите в строку для ребра c.
Хорошо, эта таблица легко читается для обхода CW-порядка;для CCW вы должны подумать, "с какого края я пришел, когда прошел этот край назад".По сути, вы получаете следующий край в порядке CCW, взяв в этом случае левый ход-предшественник b и продолжая ввод строки для края b таким же образом.
Теперь вставка иудаление: ясно, что вы не можете просто удалить ребро и подумать, что график все равно будет состоять только из треугольников;во время удаления необходимо соединить две вершины, например, X и Y в графике.Для этого сначала нужно убедиться, что везде, где упоминается ребро a, мы должны исправить это упоминание.
Так где же можно сослаться на a?только в ребрах b,c,d and e (все остальные ребра слишком далеки, чтобы знать a), плюс в таблице вершин -> ребер, если она у вас есть (но давайте рассмотрим таблицу ребер только в этом примере).
В качестве примера того, как мы должны исправить края, давайте рассмотрим c.Как и a, c имеет левый и правый пре- и преемник (так что 4 ребра), какой из них является a?Мы не можем знать это без проверки, потому что запись таблицы для c может иметь узел Y в его начальном или конечном узле.Таким образом, мы должны проверить, какой это, давайте предположим, что мы находим, что c имеет Y в своем Начальном узле, тогда мы должны проверить, является ли a c's правильным предшественником (который это и который мы выясняем,просматривая запись c's и сравнивая ее с a) ИЛИ является ли она c's правильной преемницей .«Преемник ??»Вы могли бы спросить?Да, потому что помните, что две колонки "влево" относятся к направлению края назад.Итак, теперь мы обнаружили, что a является c's правым предшественником, и мы можем исправить эту ссылку, вставив a's правого предшественника.Продолжите с другими 3 ребрами, и вы закончите с таблицей ребер.Исправление дополнительного Node->Vertices, конечно, тривиально, просто посмотрите на записи для X и Y и удалите a там.
Добавление ребер - , в основном - обратная сторона этого исправления 4 других ребер, НО с небольшим поворотом.Позволяет вызвать узел, который мы хотим разделить Z (он будет разделен на X и Y).Вы должны позаботиться о том, чтобы разбить его в правильном направлении, потому что вы можете объединить либо d и e в узле, либо e и c (например, если новое ребро горизонтальное, а не вертикальное *)1079 * в графике)!Сначала вы должны выяснить, между какими двумя ребрами будущего X и между какими двумя ребрами Y добавляется новое ребро: вы просто выбираете, какие ребра должны быть на одном узле, а какие на другомузел: в этом примере графика: выберите, что вы хотите b, c и 2 ребра к северу между ними на одном узле, и из этого следует, что другие ребра находятся на другом узле, который станет X,Затем путем вычитания вектора вы обнаружите, что новое ребро a должно находиться между b и c, а не между, скажем, c и одним из 2 ребер на севере.Вычитание вектора - это желаемое положение нового X минус желаемое положение Y.