Por favor, veja a imagem:http: //i.stack.imgur.com/NPUmR.jp

Tenho um gráfico não direcionado que contém um ou mais subgráficos conectados. O gráfico é definido por um conjunto de pares ordenados de vértices conectados. Pode haver até 300 vértices. O gráfico é plan

Preciso identificar polígonos, como mostra a imagem. Cada uma das áreas coloridas em um polígono separado. Uma heurística aproximada pode ser que os polígonos são "regiões fechadas" entre os loops de borda fechada (ciclos) no gráfico. Foi sugerido em postagens semelhantes que os ciclos podem ser identificados usando uma travessia de profundidade primeiro e marcando os vértices visitado

No entanto, não tenho certeza de como proceder depois disso para obter a saída desejada, como mostrado na image

Requirements:

i) Os polígonos não devem se sobrepor ou cruzar. ou seja: o ciclo ABFHDCA não é um polígono válido, pois ele se sobrepõe ao polígono FHGE. O ciclo ABFEGHDCA é um polígono válido.

ii) O polígono pode ter 3 ou mais arestas e os polígonos devem ser delimitados pelas arestas do gráfico. XYZ é um polígono válido, embora desconectado do restante dos vértices do gráfic

iii) Vértices como K e L (isto é, folhas) não formam partes dos polígonos. Não nos importamos com a vantagem JK.

Atualizar iv) Nas arestas do gráfico não se cruzam. O único lugar em que duas arestas podem se encontrar é em um vértice. Isso é garantido no caso de um estágio / algoritmo anterio

Questões

Estou no caminho certo com o DF travesal para encontrar a abordagem dos ciclos? A travessia do DF me daria todos os ciclos (simples) que preciso considerar nesses casos, especialmente com o XYZ sendo desconectado do restante do gráfic

Existe um algoritmo alternativo existente para resolver esse problem

Notas Adicionais

a) Estou tendo problemas para definir esse problema em termos geométricos de computação mais específicos, por isso estou tentando encontrar polígonos em um gráfico não direcionado. Devo admitir que faz anos desde que estudei teoria dos grafos. Estou atualizando agora.

b) Uma solução para isso não parece um algoritmo de casco côncavo / convexo. Estamos falando de um conjunto de arestas conectadas - polígonos verdadeiros, não apenas uma nuvem de pontos que precisa ser englobada.

c) O exemplo acima é o que eu poderia apresentar a curto prazo. Eu acho que abrange a maioria dos casos "de ponta" (trocadilhos):)

Similar Solutions Encontrei um post semelhante, masa solução aceita parece não gerar os ciclos corretos para este exempl

Desde já, obrigado