Detectar anéis / circuitos de voxels conectados
Eu tenho uma estrutura de voxel esqueletizada que se parece com isso:
A estrutura real é significativamente maior que este exemplo. Existe alguma maneira de encontrar os anéis fechados na estrutura? Tentei convertê-lo em um gráfico e usar abordagens baseadas em gráfico, mas todos eles têm o problema de que um gráfico não possui informações espaciais da posição do nó e, portanto, um gráfico pode ter vários anéis homólogos.
Não é possível encontrar todos os anéis e filtrar os de interesse, pois o gráfico é muito grande. O tamanho dos anéis varia significativamente.
Obrigado pela sua ajuda e contribuição!
Qualquer abordagem de linguagem e pseudo-código são bem-vindos, embora eu trabalhe principalmente em Python e Matlab.
EDITAR:
Não, o gráfico não é plano. O problema com a base do ciclo do gráfico é o mesmo que com outras abordagens simples baseadas em gráfico. O gráfico não possui informações espaciais e diferentes configurações espaciais podem ter a mesma base de ciclo, portanto, a base de ciclo não corresponde necessariamente aos ciclos ou furos no gráfico.
Aqui está a matriz de adjacência no formato esparso:
NodeID1 NodeID2 Weight
Pastebin com matriz de adjacência
E aqui estão as coordenadas X, Y, Z correspondentes para os nós do gráfico:
X Y Z
Pastebin com coordenadas do nó
(A estrutura real é significativamente maior que este exemplo)