Пожалуйста, смотрите изображение: http://i.stack.imgur.com/NPUmR.jpg
У меня есть ненаправленный граф, который содержит один или несколько связанных подграфов.Граф определяется набором упорядоченных пар связных вершин.Может быть до 300 вершин.График плоский.
Мне нужно идентифицировать полигоны, как показано на рисунке.Каждая из цветных областей в отдельном многоугольнике.Грубая эвристика может заключаться в том, что полигоны являются «закрытыми областями» между замкнутыми краевыми петлями (циклами) в графе.В аналогичных публикациях было предложено, что циклы могут быть идентифицированы с помощью обхода в глубину и маркировки посещенных вершин
Однако я не уверен, как действовать после этого, чтобы получить желаемый результат, как показано на рисунке.
Требования:
i) Полигоны не должны пересекаться или пересекаться.то есть: цикл ABFHDCA не является допустимым многоугольником, поскольку он будет перекрываться с многоугольником FHGE.Цикл ABFEGHDCA является допустимым многоугольником.
ii) Многоугольник может иметь 3 или более ребер, и многоугольники должны быть ограничены ребрами графа.XYZ является допустимым многоугольником, хотя он не связан с остальными вершинами графа.
iii) Вершины, подобные K и L (т.е. листья), не образуют части многоугольников.Нас не волнует край JK.
Обновление: iv) В графе грани не пересекаются друг с другом.Единственное место, где могут встретиться два ребра, это вершина.Это гарантировано в случае предыдущего этапа / алгоритма.
Вопросы:
Я на правильном пути с обходом DF, чтобы найти подходы циклов?Даст ли мне обход DF все (простые) циклы, которые мне нужно рассмотреть в таких случаях, особенно с отключением XYZ от остальной части графика?
Существует ли альтернативный алгоритм для решения этой проблемы?
Дополнительные примечания:
a) У меня проблемы с определением этой проблемы в более конкретных геометрических терминах вычислений, поэтому я придерживаюсь поиска полигонов в неориентированном графе.Я должен признать, что прошли годы с тех пор, как я изучал теорию графов.Я чищу это сейчас.
б) Решение этого не похоже на алгоритм вогнутой / выпуклой оболочки.Мы говорим о наборе связанных ребер - настоящих многоугольников, а не только о облаке точек, которое необходимо охватить.
в) Приведенный выше пример - то, что я мог бы придумать в короткие сроки.Я думаю, что это покрывает большинство «крайних» случаев (каламбур) :)
Похожие решения
- Я нашел похожий пост, но принятое решение не делаетКажется, t генерирует правильные циклы для этого примера.
Заранее спасибо!