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

Question

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

Есть ли хорошие решения этой проблемы?

---

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

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

Кто-нибудь видит проблему с этим? Будет ли это даже работать?

Answer 1

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

Answer 2

«Перекрестный край», как вы его называете, обычно известен как аккорд . Таким образом, ваша задача - найти все аккордовые циклы.

Эта статья , похоже, может помочь.

Answer 3

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

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

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

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

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