Por favor, vea la imagen:http: //i.stack.imgur.com/NPUmR.jp

Tengo un gráfico no dirigido que contiene uno o más gráficos secundarios conectados. El gráfico está definido por un conjunto de pares ordenados de vértices conectados. Puede haber hasta 300 vértices. El gráfico es plano.

Necesito identificar polígonos como se muestra en la Imagen. Cada una de las áreas coloreadas en un polígono separado. Una heurística aproximada podría ser que los polígonos son "regiones cerradas" entre bucles de borde cerrado (ciclos) en el gráfico. Se ha sugerido en publicaciones similares que los ciclos se pueden identificar utilizando un recorrido de Profundidad Primero y marcando vértices visitados.

Sin embargo, no estoy seguro de cómo proceder después de esto para obtener la salida deseada como se ve en la imagen.

Requisitos:

i) Los polígonos no deben solaparse ni intersectarse. es decir: el ciclo ABFHDCA no es un polígono válido ya que esto se superpondría con el polígono FHGE. El ciclo ABFEGHDCA es un polígono válido.

ii) El polígono puede tener 3 o más bordes y los polígonos deben estar delimitados por los bordes del gráfico. XYZ es un polígono válido aunque desconectado del resto de los vértices del gráfico.

iii) Los vértices como K y L (es decir, hojas) no forman parte de los polígonos. No nos importa Edge JK.

Actualizar iv) En el gráfico, los bordes no se cruzan. El único lugar donde dos bordes pueden encontrarse es en un vértice. Este es el caso garantizado por una etapa / algoritmo anterior.

Preguntas:

¿Estoy en el camino correcto con la travesía del DF para encontrar el enfoque de ciclos? ¿El recorrido DF me daría todos los ciclos (simples) que debo considerar en tales casos, especialmente con XYZ desconectado del resto del gráfico?

Existe un algoritmo alternativo existente para resolver este problema?

Notas adicionales

a) Tengo problemas para definir este problema en términos geométricos de cálculo más específicos, por lo que me quedo con la búsqueda de polígonos dentro de un gráfico no dirigido. Debo admitir que han pasado años desde que estudié teoría de grafos. Lo estoy repasando actualmente.

b) Una solución a esto no parece un algoritmo de casco cóncavo / convexo. Estamos hablando de un conjunto de bordes conectados: polígonos verdaderos, no solo una nube de puntos que debe abarcar.

c) El ejemplo anterior es lo que se me ocurrió a corto plazo. Creo que cubre la mayoría de los casos de "borde" (juego de palabras):)

Similar SolutionsEncontré una publicación similar perola solución aceptada no parece generar los ciclos correctos para este ejemplo.

¡Gracias por adelantado