pequeño ciclo de búsqueda en un gráfico plano

Question

Tengo un gráfico plano , que es un gráfico donde cada nodo tiene una ubicación y no se cruzan 2 bordes, y quiero encontrar todos los ciclos que no tengan bordes que los crucen.

¿Hay alguna buena solución conocida para este problema?

---

Lo que planeo hacer es una especie de A * como solución:

• inserte cada borde en un montón mínimo como ruta
• extienda el camino más corto con todas las opciones
• elimine las rutas que vuelven a otro inicio que no sea allí (podría no ser necesario)
• elimine las rutas que serían las terceras en usar el ángulo dado

¿Alguien ve un problema con esto? ¿Funcionará incluso?

Answer 1

Mi primer instinto es utilizar un método similar a un muro siguiendo laberinto. Esencialmente, siga los bordes y siempre saque el borde más a la derecha de un vértice. Cualquier ciclo que encuentres con este método será el límite de una cara. Tendrá que realizar un seguimiento de qué bordes ha atravesado en qué dirección. Una vez que ha atravesado un borde en ambas direcciones, ha identificado las caras que separa. Una vez que se hayan atravesado todos los bordes en ambas direcciones, habrá identificado todas las caras por sus límites.

Answer 2

Un '' borde de cruce '', como lo llama, generalmente se conoce como un acorde . Por lo tanto, su problema es encontrar todos los ciclos sin acordes.

Este documento parece que puede ayudar.

Answer 3

Una manera simple de hacer esto es simplemente salir y enumerar cada cara. El principio es simple:

• Mantenemos banderas de 'visita-a' y 'visita-ß' para cada borde, y un par de listas doblemente enlazadas de bordes no visitados para cada bandera. La división 'a' y 'ß' debe corresponder a una partición del plano en la línea correspondiente al borde en cuestión; qué lado es a y qué lado es ß es arbitrario.
• Para cada vértice V:
  • Para cada par de aristas adyacentes E = (V_1, V), E '= (V_2, V) (es decir, ordenar por ángulo, tomar pares adyacentes, así como primero + último):
  • Determine en qué lado S de E (S = a o ß) se encuentra V_2.
  • Recorre el mosaico, comenzando en V, usando el lado S de E, como se describe a continuación:

Recorrer el mosaico es realizado por:

• Let V = V_init
• bucle:
  • V_next = el vértice de E que no es V
  • E '= El borde adyacente a E desde V_next que está en el lado actual de E
  • S '= El lado de E' que contiene V
  • Si V_next = V, hemos encontrado un bucle; registre todos los bordes por los que pasamos en el camino y marque esos pares de bordes como visitados.
  • Si E '= E (solo hay un borde), entonces hemos llegado a un callejón sin salida; abortar esta caminata
  • De lo contrario, deje V = V_siguiente, E = E ', S = S' y continúe.

Espero que esto tenga sentido; quizás necesite algunos diagramas para explicar ...