Найти все выпуклые подграфы в графе

[undefined]

Добрый день.

Имеется 2D граф из 4-ех вершин и 4-ех ребер в форме прямоугольника.
Потом этот граф режется произвольной плоскостью.
Добавляются новые вершины и ребра вдоль линии разреза.
Повторяем процедуру нарезки 50 раз
Полученый граф будет соответствовать раскройке некоторой оригами-фигуры. Т.е. сложили 50 раз лист бумаги по произвольной линии, развернули и получился наш граф.

Инстинктивно кажется, что состоять такой граф будет из выпуклых N-угольников(полигонов), склееных вдоль границ.
Задача найти все эти N-угольники.

На первый взгляд несложно.
- Берем любое непройденное ребро
- Заносим его в result
- из всех следующих за ним ребер выбираем то, по которому повернем на максимальный угол
- заносим такое ребро в result
- идем по ребрам дальше, пока не вернемся в стартовое.
- как вернулись - выпуклый цикл найден
- у найденного цикла помечаем все ребра как пройденные(при этом неграничные ребра надо пройти по 2 раза т.к. они соединяют 2 полигона)
- повторяем цикл поиска пока есть непройденные ребра

Короче это flood fill, только для полигонов.

Для простых кейсов, алгоритм работает без ошибок(нашлись все 9 полигонов)
https://imgur.com/RseBUZr

А вот в сложных случаях бывает пропускает полигоны
https://imgur.com/BHLBE2L

Дебаг показал, что это из-за того, что существуют ребра, из которых есть путь по непройденным ребрам,который НЕ ведет в стартовое ребро. На самом деле, этот путь ведет в одно из следующих после старта ребер.
От этого алгоритм зацикливается, т.к. пройденными я помечаю ребра уже после нахождения цикла. В результате остаются ребра, которые нельзя протрассировать и вернуться в начало.
От чего в графе появляются дырки(см. скрин 2)
Мне казалось, что алгоритм выше должен исключать такие случаи, но очевидно это не так.

Может кто-нибудь подкинет идею, как бы так хитро обойти граф, разбив его на множество выпуклых N-угольных полигонов?

PS: Замечал, на древних компах, что инструменту flood fill не всегда с первого раза удавалось закрасить область(алгоритм сам себе блокирует доступ в некоторые области). Надо было оставшиеся дырки дозакрашивать вручную.
Подозреваю, что нечто похожее происходит и в моем случае.

[dgwuqtj]

Видимо, у вас граф неправильно задан изначально, потому что такого действительно быть не должно. Как вы сам граф получаете?

[undefined]

Граф задается списком ребер
Каждое ребро хранит 2 ссылки на вершины(начало и конец)+ интовая переменная traversed(сколько раз прошлись по ребру)
Каждая вершина хранит список ребер, которым принадлежит

При рассечении ребра плоскостью, его конец перемещается в точку пересечения,а в список ребер добавляется новое ребро от точки пересечения до конца рассекаемого ребра.
При трассировке, все ребра, принадлежащие концу текущего ребра(кроме самого текущего ребра конечно же), поворачиваются так, чтобы они исходили из конца текущего ребра.
Каждое ребро трассируется по и против часовой стрелки.

Изначальный граф задан 4-мя ребрами против часовой стрелки
Результирующий граф получается после череды рассечений

[dgwuqtj]

Ну, тогда где-то в коде ошибка. Ещё могла бы быть проблема с округлениями, вы же наверняка работаете с числами с плавающей запятой, но на картинке пропущенный треугольник не сильно вырожденный.

Вообще можно прямо в процессе рассечений поддерживать список всех областей, рассечение сводится к разрезанию кучи таких областей на 2 части. Другими словами, каждое ребро имеет смысл хранить в двух экземплярах, в одну и в другую сторону (кроме граничных, их в одном экземпляре, против часовой стрелки для определённости). Также для каждого такого ориентированного ребра надо поддерживать указатель на следующее ребро при обходе области слева от него и указатель на противоположное ребро (когда оно есть). Может, это избыточно по памяти, зато при добавлении каждой прямой легко проверять, что ничего не сломалось.