Quiero dibujar un mapa de polígonos 2D basado en datos proporcionados por otra fuente para facilitar el análisis de acciones en el mapa. Los datos tienen el siguiente 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']
...El primer número es la ID de un nodo, la siguiente lista contiene las ID de sus vecinos. Como el número de vecinos de un nodo difiere, necesito dibujar un mapa poligonal.
Así que intenté usar los polígonos de Voronoi para la representación del mapa. El problema es: ¿cómo puedo determinar los puntos para satisfacer todas las relaciones de vecindario? Supongo que mi primer intento es más o menos un error en mi ciclo de prueba y error. Utilicé la herramienta sfdp de graphviz para obtener las posiciones de puntos del gráfico:
El uso de las posiciones de los puntos resultó en la siguiente representación del mapa:
El problema de este enfoque es que, por ejemplo, los nodos 4 y 1 son vecinos, pero en el diagrama de Voronoi no lo son debido a la posición de los nodos. Entonces para mí este enfoque falló.
En Google, encontré muchos tutoriales que generan mapas con polígonos o mosaicos, pero aún no he descubierto cómo puedo crear un mapa para mis datos dados. Supongo que hay un enfoque que usa (múltiples) hexágonos / triángulos / cuadrados o una mezcla para lograr lo que necesito, pero no sé qué buscaré.
¿Hay una palabra clave o un algoritmo que me pueda ayudar aquí?
Actualización / Resultado : Para completar: Este es mi resultado después de usar las sugerencias de la respuesta aceptada:
Respuestas:
Lo que quieres es producir un gráfico dual ; es decir, un gráfico producido al convertir caras en vértices y conectarlas en función de caras adyacentes en el gráfico original. Ejemplo:
El problema, como puede ver, es que si desea mantener el mismo diseño del gráfico, obtendrá algunos bordes realmente curvos en el gráfico dual. Además, a menudo terminará con un multigrafo , un gráfico donde algunos vértices tienen múltiples bordes entre ellos. Sin embargo, se garantiza que sea plano, así que eso es algo.
Para usar su ejemplo, podemos producir el gráfico dual en los siguientes pasos:
Paso 1: para cada cara en el gráfico original, cree un vértice
Tenga en cuenta que creamos un "anillo" externo para representar el "vértice" más externo; esto es para que podamos tener un gráfico más bonito al final, sin los bordes curvos locos.
Paso 2: para cada borde en el gráfico original, conecte los dos vértices de la cara con un borde
Además, tendrá que hacer algo para que estos bordes no se superpongan entre sí. La brecha entre 3 y 12 es especialmente problemática. Es posible que estos nuevos bordes deban ser flexibles para que esto sea posible. Es lo que obtienes por tener un gráfico cóncavo.
Paso 3: riesgo de juego
fuente
Si la primera imagen, donde cada punto es un pequeño cuadrado con cierto color, es lo que está buscando, debe construir la triangulación de Delaunay.
fuente