Algoritmo de mosaico/Estructuras de datos?

Question

Estoy pensando en crear un programa que me permita jugar o resolver acertijos slitherlink, como en krazydad.com. Consiste en fichas de 4, 5, 6, 7 y 8 lados. Todas las baldosas, excepto las de siete lados, parecen tener lados con la misma longitud, con los lados entre dos baldosas de siete lados (y por lo tanto, conectando baldosas de cinco lados con baldosas de 4 lados) con lados de aproximadamente el 70% de la longitud normal. Como puede ver en la imagen siguiente, los octágonos están rodeados de pentágonos y hexágonos alternados. Estos están unidos a otros a por los lados de los hexágonos. Adjunta a las puntas de los pentágonos hay líneas más pequeñas que conectan con cuadrados que se conectan a otros grupos. Alrededor de los cuadrados se forman figuras de siete lados con dos lados cortos. Creo que el borde exterior se define omitiendo las fichas que están demasiado lejos del centro.

Para una estructura de datos Creo que necesito un gráfico que conecta todos los nodos. Puedo dejar que el usuario haga clic para colocar una línea continua en el enlace más cercano, y puedo verificar bucles o demasiadas líneas que ingresan a un nodo con bastante facilidad. También necesitaré crear mosaicos y asociar líneas a ellos, con líneas internas asignadas a ambos mosaicos, pero tratadas como una línea.

En cuanto a la configuración, estoy pensando en calcular manualmente los puntos y definir el conjunto mínimo de mosaicos repetidos (1 8, 4 5, 4 6, 4 7 y 1 4) y colocarlos al lado de cada uno otro. Al colocar, verificaría los puntos cercanos existentes a cada uno que estoy colocando y los combinaría si los encontrara. Entonces necesitaría verificar si hay líneas duplicadas y unirlas también.

¿Existe una forma más fácil o más clara de A) generar el mosaico o B) fusionar los nodos y los enlaces al hacer el mosaico?

Answer 1

algunas observaciones que podrían ayudar:

• si se une a los centros de los polígonos vecinos que tienen una triangulación de Delaunay (1).

• la doble (2) de la triangulación de Delaunay es el gráfico anterior (con un poco diferentes longitudes de los bordes, pero se puede ajustar que si es necesario)

• hay una discusión aquí (3) de cómo generar gráficos de Delaunay triangulaciones

así, poner que juntos, usted podría:

• generar los centros de las teselas (ver a continuación)

• construir la triangulación de delaunay de los centros de teselas (uniendo neigbours).

• encontrar el doble para obtener el gráfico que desea (el proceso de encontrar la doble deben ser apoyados por una buena biblioteca gráfica)

para generar el patrón de los centros de azulejos, tomar el conjunto mínimo y comience con el centro 8. Para cada rotación de 90 grados, agregue el conjunto mínimo (girado) (más un 8 además del que está rotando), eliminando los duplicados. luego haz lo mismo en los 8s que hayas agregado (recurse o usa una pila).

una vez que tenga los centros, no estoy seguro de cuál sería la mejor forma de conectar a los vecinos; desea una forma eficiente de generar un conjunto de candidatos. pero no es un problema difícil, simplemente complicado (una solución "sofisticada" sería quadtree o hashes espaciales, pero bastaría con un binning crudo).