нахождение малого цикла в плоском графе

Question

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

Известны ли какие-либо хорошие решения этой проблемы?

---

То, что я планирую сделать, это своего рода A* подобное решение:

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

Кто-нибудь видит проблему в этом?Сработает ли это вообще?

Answer 1

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

Answer 2

"Пересекающийся край", как вы это называете, обычно известен как аккорд.Таким образом, ваша задача состоит в том, чтобы найти все циклы без аккордов.

Этот документ похоже, это может помочь.

Answer 3

Простой способ сделать это - просто выйти и перечислить каждую грань.Принцип прост:

• Мы поддерживаем флаги "α-посещенных" и "β-посещенных" для каждого ребра и пару двусвязных списков не посещенных ребер для каждого такого флага.Разделение 'α' и 'β' должно соответствовать разделению плоскости на линии, соответствующей рассматриваемому краю;какая сторона равна α, а какая - β, является произвольной.
• Для каждой вершины V:
  • Для каждой смежной пары ребер E = (V_1, V), E'=(V_2, V) (т.е. отсортируйте по углу, возьмите смежные пары, а также first+last):
  • Определите, на какой стороне S от E (S=α или β) лежит V_2.
  • Пройдитесь по плитке, начиная с V, используя сторону S от E, как описано ниже:

Ходьба по плитке выполняется:

• Пусть V = V_init
• Петля:
  • V_next = вершина E , которая не является V
  • E' = Соседнее ребро к E от V_next, которое находится на текущей стороне E
  • S' = сторона E', которая содержит V
  • Если V_next = V, мы нашли цикл;запишите все ребра, мимо которых мы проходили по пути, и пометьте эти пары ребер как посещенные.
  • Если E' = E (есть только одно ребро), то мы зашли в тупик;прервите эту прогулку
  • В противном случае пусть V = V_next, E = E', S = S' и продолжайте.

Я надеюсь, что это имело смысл;возможно, для объяснения этого нужны какие-то диаграммы...