Dado un conjunto de mosaicos en una cuadrícula, quiero determinar:
- Si los azulejos hacen una figura cerrada
- Si las fichas forman una figura cerrada cuando cuenta los lados del tablero como un borde de la figura
- Si alguna de las dos afirmaciones anteriores es verdadera, qué fichas adicionales se encuentran dentro de la figura adjunta se forman las fichas iniciales.
El jugador comenzará presionando hacia abajo una ficha, luego arrastrará su dedo hacia otras fichas para crear una cadena de fichas del mismo color. Comprobaré a medida que avance para ver si el siguiente mosaico es válido. Ex. Si el jugador comienza en una ficha roja, su único movimiento válido siguiente es una ficha roja adyacente (las diagonales sí cuentan). Cuando el usuario levanta el dedo, necesito poder verificar los 3 elementos anteriores.
Así que mi pensamiento inicial fue que, dado que estaba comprobando la validez de la cadena cada vez que iba, cuando el jugador levantaba el dedo, podía comprobar si la primera y la última ficha eran adyacentes. (Ya sé que son del mismo color). Si fueran adyacentes, tenía el presentimiento de que había hecho una figura cerrada, y que iba a venir aquí para tratar de ver si me faltaba algo grande y algún tipo de prueba lógica / matemática de que mi presentimiento era correcto (o un ejemplo que demuestra que es incorrecto)
Pero fue entonces cuando pensé en el elemento número 2: también tengo que tener en cuenta las cadenas que usan un borde del tablero como un lado de la figura adjunta. En ese caso, el primer y el último elemento de la cadena no serían adyacentes, pero aún tendría una figura cerrada. Así que ahora estoy de vuelta al punto de partida, un poco.
¿Qué puedo hacer con esta cadena de coordenadas de cuadrícula para determinar si forman una figura cerrada o no? Y una vez que no sé que tengo una figura cerrada, ¿cuál es la mejor manera de obtener una lista adicional de todas las fichas que caen dentro de sus límites?
Arriba he dibujado imágenes de lo que espero que puedan ser los 4 resultados posibles de esta prueba.
La cadena no hace una figura cerrada.
La cadena hace una figura cerrada.
Si cuenta los lados del tablero como un borde (o más de un borde) de la figura, la cadena forma una figura cerrada.
La cadena forma una figura cerrada, pero hay puntos de datos adicionales (seleccionados válidamente por el usuario como parte de la cadena) que no forman parte de la figura que se crea.
El caso 4 es el más complicado, porque tendrías que extraer los eslabones de la cadena "extra" para encontrar la figura adjunta y las piezas que caen dentro de ella (pero no alrededor del área "no cerrada").
Entonces ... ¿Alguien tiene una idea de una buena manera de resolver esto, o simplemente un punto de partida para mí? Estoy yendo en círculos en este punto y podría usar otro par de ojos.
Respuestas:
1. Detectando un bucle de mosaicos
El problema parece similar a la detección de un ciclo (bucle) en un gráfico, ver aquí o aquí .
V
de ese gráficoG=(V, E)
son los mosaicos,e = (v1, v2)
existe un borde entre dos nodos diferentes, si los mosaicos son vecinos directos o diagonales2. Manejo de la caja del borde de la pantalla
El borde de la pantalla consiste en esas fichas imaginarias que formarían un borde ancho de una ficha alrededor de la pantalla de las fichas visibles.
Según su especificación, parte del borde de la pantalla formaría parte implícita de un circuito cerrado. Solo para detectar un circuito cerrado, sería suficiente extender el gráfico
G
a un gráficoG'
respetando la conexión a través de esta regla:Por lo tanto, los mosaicos en (0,0) y (1,0) serían parte de un ciclo cerrado, junto con los "mosaicos de borde" (-1,0), (-1, -1), (0, -1) , (1, -1).
3. La parte interior de un área en bucle
Me gustaría ir en una dirección similar a lo que sugirió el usuario Arthur Wulf White :
Limitando el conjunto de mosaicos que tenemos que examinar por el cuadro delimitador de los mosaicos de bucle.
Luego, usando un relleno de inundación para seleccionar todos los mosaicos dentro del cuadro delimitador que son exteriores o interiores al circuito cerrado. Solo puede ser uno de esos dos casos. Cuál tenemos que averiguar después.
También sería una buena idea extender el cuadro delimitador con una baldosa en cada dirección, dando como resultado,
extbb
por lo que terminamos con un conjunto de puntos exteriores conectados, en caso de que comencemos el relleno de inundación con una baldosa exterior.Una vez que tengamos el área de relleno de inundación, también calcularíamos su cuadro delimitador, el
ffbb
. En caso de que empecemos con un mosaico exterior, debe ser idéntico al cuadro delimitador de bucle extendido.En caso de que empecemos con un mosaico interior, debería producir un cuadro delimitador claramente más pequeño, porque los mosaicos de bucle deben intercalarse entre ambos cuadros delimitadores.
El mosaico inicial para el relleno de inundación podría ser cualquier mosaico dentro del
extbb
cual sea un mosaico libre. Tal vez elegir uno al azar es el mejor enfoque.Si supiera antes que el interior es más pequeño que el exterior, comenzaría alrededor del centro de masa de los puntos de bucle que está en el interior de muchas áreas (ejemplo contrario: área en forma de C), de lo contrario en el borde de la
extbb
. Pero no tengo idea de cómo estimar esto.Observaciones finales
Normalmente, diría que una simple caminata comenzando desde un mosaico y manteniendo una lista de mosaicos visitados sería suficiente para detectar un ciclo, pero esa condición de límite de pantalla podría generar un gráfico más complicado, por lo que debe estar seguro con un algoritmo gráfico. .
A continuación se muestra un ejemplo en el que el interior no está conectado, por otro lado, la detección del ciclo debe encontrar dos bucles en ese caso, uno debe descartarse.
fuente
Puede resolver esto de la siguiente manera:
Para hacer una, iterar sobre todos los azulejos en la cadena y encontrar su
minX
,minY
,maxX
ymaxY
y que es su cuadro delimitador o AABB.Dos es trivial.
Iterar sobre el marco es simple, solo asegúrese de no inundar fuera de la cuadrícula. Puedes aprender a rellenar en Wikipedia .
Para el número cuatro, puede comenzar marcando solo las fichas adyacentes a la cadena. Podrías rellenar desde cualquier mosaico que encuentres que no esté marcado para ubicar más mosaicos.
fuente
Su intuición es correcta, suponiendo que la cadena termina tan pronto como el usuario intenta seleccionar un mosaico que ya ha seleccionado. En ese caso, la forma en general se parece a un lazo, en su imagen (4). Si pueden seguir deslizando, pueden dibujar muchos bucles y las cosas se vuelven más complicadas. Lo que quiere hacer es responder la pregunta de puntos en el polígono .
Primero, necesitamos definir el problema. Voy a suponer que la situación se ve como (2), es decir, se ha quitado cualquier cola, y el final se conecta de nuevo al inicio, de modo que cada mosaico tiene exactamente un "predecesor" y exactamente un "sucesor" en la cadena (donde el predecesor del sucesor del mosaico X es siempre el mosaico X). Además, si sigue a los "sucesores" durante el tiempo suficiente, eventualmente volverá a donde comenzó. Puede usar la sugerencia de Gurgadurgen para detectar si el bucle realmente se cruza sobre sí mismo en cualquier momento. Suponiendo que finaliza la entrada del usuario cuando lo hace, se verá como una serie de nodos en una línea, seguido de un bucle. Puede quitar la línea del get the loop.
Ahora, para cada fila hacemos lo siguiente:
Ahora tome todos los mosaicos que están IN, agregue los mosaicos en el borde (incluida una cola si lo despojó antes o no, según su elección), y llame a eso la región.
Si desea permitir que el usuario use bordes, recuerde que esto no define e IN / OUT en el tablero, sino que lo divide en dos partes. Puede seleccionar la región más pequeña, por ejemplo, o requerir que el usuario use dos lados adyacentes (es decir, el izquierdo y el inferior, pero no el superior / inferior o el izquierdo / derecho).
Una optimización es que solo necesita hacer filas que tengan algún borde (si no puede usar los lados). Supongo que su placa es lo suficientemente pequeña como para que iterar sobre cada mosaico y hacer un cálculo muy simple no sea un problema, incluso en el sistema móvil más débil. (Después de todo, debe renderizarlos, lo cual es una tarea mucho más compleja).
fuente