Quero desenhar um mapa de polígono 2D com base nos dados fornecidos por outra fonte para facilitar a análise das ações no mapa. Os dados têm o seguinte formato:
1 ['2', '4', '5', '7', '17', '10']
2 ['1', '3', '4']
3 ['2', '11', '4']
4 ['1', '2', '3', '11', '13', '18', '5']
5 ['1', '4', '18', '17']
6 ['7', '8']
...
O primeiro número é o ID de um nó, a lista a seguir contém os IDs de seus vizinhos. Como o número de vizinhos de um nó difere, preciso desenhar um mapa poligonal.
Então, tentei usar polígonos Voronoi para a representação do mapa. O problema é: como posso determinar os pontos para satisfazer todas as relações de vizinhança? Acho que minha primeira tentativa é mais ou menos um erro no meu ciclo de tentativas e erros. Eu usei o SFDP ferramenta de graphviz para obter as posições de ponto do gráfico:
O uso das posições dos pontos resultou na seguinte representação do mapa:
O problema dessa abordagem é que, por exemplo, os nós 4 e 1 são vizinhos, mas no diagrama de Voronoi eles não são por causa da posição dos nós. Então, para mim, essa abordagem falhou.
Pesquisando no Google, encontrei muitos tutoriais gerando mapas com polígonos ou blocos, mas ainda não descobri como posso criar um mapa para meus dados. Eu acho que existe uma abordagem usando (múltiplos) hexágonos / triângulos / quadrados ou uma mistura para alcançar o que eu preciso, mas não sei o que devo procurar.
Existe uma palavra-chave ou um algoritmo que pode me ajudar aqui?
Atualização / Resultado : Para completar: Este é o meu resultado depois de usar as sugestões da resposta aceita:
Respostas:
O que você quer é produzir um gráfico duplo ; isto é, um gráfico produzido convertendo faces em vértices e conectando-as com base em faces adjacentes no gráfico original. Exemplo:
O problema, como você pode ver, é que, se você quiser manter o mesmo layout do gráfico, obterá algumas arestas realmente curvas no gráfico duplo. Além disso, muitas vezes você acaba com uma multigráfica - um gráfico em que alguns vértices têm várias arestas entre eles. É garantido que seja plano, então isso é algo.
Para usar seu exemplo, podemos produzir o gráfico duplo nas seguintes etapas:
Etapa 1: para cada face no gráfico original, crie um vértice
Observe que criamos um "anel" externo para representar o "vértice" mais externo - é para que possamos ter um gráfico com melhor aparência no final, sem as arestas curvas e malucas.
Etapa 2: para cada aresta no gráfico original, conecte os dois vértices da face a uma aresta
Além disso, você terá que fazer algo para que essas arestas não se sobreponham. A diferença entre 3 e 12 é especialmente problemática. Essas novas arestas podem precisar ser flexíveis para tornar isso possível. É o que você ganha por ter um gráfico côncavo.
Etapa 3: jogar risco
fonte
Se a primeira imagem, em que cada ponto é um pequeno quadrado com certa cor, é o que você está procurando, você precisa construir a triangulação do Delaunay.
fonte