Пожалуйста, смотрите изображение:http://i.stack.imgur.com/NPUmR.jpg

У меня есть неориентированный граф, который содержит один или несколько связанных подграфов. Граф определяется набором упорядоченных пар связных вершин. Может быть до 300 вершин. График плоский.

Мне нужно идентифицировать полигоны, как показано на рисунке. Каждая из цветных областей в отдельном многоугольнике. Грубая эвристика может заключаться в том, что полигоны являются «закрытыми областями» между замкнутыми краевыми петлями (циклами) в графе. В аналогичных публикациях было предложено, что циклы могут быть идентифицированы с помощью обхода в глубину и маркировки посещенных вершин.

Однако я не уверен, как действовать после этого, чтобы получить желаемый результат, как показано на рисунке.

Требования :

i) Полигоны не должны пересекаться или пересекаться. Т.е. цикл ABFHDCA не является допустимым многоугольником, поскольку он будет перекрываться с многоугольником FHGE. Цикл ABFEGHDCA является допустимым многоугольником.

ii) Многоугольник может иметь 3 или более ребер, и многоугольники должны быть ограничены ребрами графа. XYZ является допустимым многоугольником, хотя он не связан с остальными вершинами графа.

iii) вершины, подобные K и L (то есть листья), не образуют части многоугольников. Нас не волнует край JK.

Обновить: iv) В графе грани не пересекаются. Единственное место, где могут встретиться два ребра, это вершина. Это гарантировано в случае предыдущего этапа / алгоритма.

Вопросов:

Я на правильном пути с обходом DF, чтобы найти подходы циклов? Даст ли мне обход DF все (простые) циклы, которые мне нужно рассмотреть в таких случаях, особенно с отключением XYZ от остальной части графика?

Существует ли альтернативный алгоритм для решения этой проблемы?

Дополнительные примечания:

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

б) Решение этого не похоже на алгоритм вогнутой / выпуклой оболочки. Мы говорим о наборе связанных ребер - настоящих многоугольников, а не просто облаке точек, которое необходимо охватить.

в) Приведенный выше пример - это то, что я могу придумать в короткие сроки. Я думаю, что это покрывает большинство «крайних» случаев (каламбур) :)

Подобные решенияЯ нашел похожий пост, нопринятое решение кажется, не генерирует правильные циклы для этого примера.

Заранее спасибо!