Найти все непересекающиеся многоугольники в списке ребер / вершин

Question

У меня есть список ребер и список вершин.Каждое ребро ссылается на две вершины, каждая вершина поддерживает список ребер.

Я хочу найти все непересекающиеся полигоны, полученные из этого графа.

Примером может быть

0,0) (4,0) (4,2) (4,4) (2,4) (2,2) (4,2) (6,2) (6,6) (0,6) (0,0)

Этот путь должен описывать каждое уникальное ребро со столкновениями в некоторых вершинах.В реальном графе вершины различны.Мне понадобятся два полигона из этого набора: (0,0) (4,0) (4,2) (2,2) (2,4) (4,4) (4,2) (6,2)(6,6) (0,6) и (2,2) (2,4) (4,4) (4,2)

Answer 1

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

Проблема также обсуждается в этой теме для случая ориентированных графов.Вы можете превратить свой граф в ориентированный граф, сделав копию каждого ребра с перевернутыми вершинами, а затем обработав его по указанию.Единственная проблема заключается в том, что каждый полигон будет найден дважды, по одному в каждом направлении обхода.Вы можете убрать это с помощью шага постобработки или, возможно, с помощью некоторой умной бухгалтерии во время работы алгоритма.

Answer 2

Ну, я думал ...

Единственные вершины, представляющие особый интерес, это вершины с более чем двумя ребрами. Найти все вершины с более чем двумя ребрами - это O (n). Тогда найти самую короткую замкнутую петлю - это то же самое, что найти наименьшую тета между заданным ребром и другим ребром в заданной вершине (если вершины - ccw, это наименьший угол по часовой стрелке от текущего ребра). Чтобы найти все самые тесные замкнутые петли, мне нужно проверить все пары ребер ccw ребра в вершине, где число ребер больше 2. Это инициализация трассы. С этого момента трасса всегда будет выбирать следующий край с наименьшим тета по часовой стрелке. Как только путь возвращается, я перехожу к следующей паре ребер в корневой вершине и снова к пути. После того, как все пары проверены, я перехожу к следующей вершине с числом ребер больше 2. Теперь, если я могу только определить, попаду ли я в известный цикл, а не в трассировку. Возможно, если первые две вершины пути встречаются в одном и том же порядке в уже известном многоугольнике ...

Как это звучит? Я знаю, что это не джикстра, но это будет работать, и, надеюсь, быстрее, чем найти все циклы грубой силы.