Universidad Politécnica de Madrid Facultad de Informática

Trabajo Fin de Carrera: 

Juegos geométricos basados en triangulaciones

Autor: Beatriz Cortés García

Tutor: Manuel Abellanas Oar

Definiciones y conceptos básicos

Juegos combinatorios

La aplicación de la que trata este trabajo fin de carrera es una serie de juegos geométricos que como indica el titulo están basados en triangulación, pero ante todo son juegos basados en la teoría de los juegos combinatorios. 

Los juegos combinatorios estudia las estrategias y  son juegos de perfecta destreza tales como el ajedrez o el Nim. Y además este tipo de juegos han sido el germen para nuevas teorías matemáticas, tal es el caso de Euler que oyó hablar del problema de los siete puentes de Könisgberg, el cual trata de la posibilidad de organizar un paseo que cruzase todos y cada uno de los puentes una sola vez. La solución de este problema dio como solución el camino euleriano, que constituyo el comienzo de una nueva rama en las matemáticas.

Para que un juego sea considerado un juego combinatorio tendrá que cumplir las siguientes reglas:

Triangulación y la fórmula de Euler

La triangulación es la división de una superficie o polígono plano en un conjunto de triángulos, normalmente con la restricción de que cada lado del triángulo se reparta entre dos triángulos adyacentes. Se demostró que a todas las superficies se puede realizar una triangulación, pero podría requerir un número infinito de triángulos. Una superficie con un número finito de triángulos en su triangulación se denomina compacta.

Una de las triangulaciones más conocidas es la triangulación de Delaunay, que es una de las triangulaciones más interesantes por ser aplicable para la resolución de multitud de problemas aparentemente sin relación entre sí, debido a sus propiedades geométricas, y por contar con algoritmos bastante eficientes para su cálculo. La definición formal de esta triangulación sería: Sea P un conjunto de n puntos de n puntos del plano, para cada triangulación T de conjunto P, el vector de ángulos es el vector formado por los ángulos de todos los triángulos de T ordenados de menor a mayor. Dado que cualquier triangulación de un conjunto de puntos tiene el mismo número de triángulos, es evidente que todos los vectores de ángulos tendrán la misma dimensión. Pues bien, se verifica que el orden lexicográfico definido en el conjunto de los vectores de ángulos de un conjunto de puntos P es un orden parcial que posee un elemento máximo, es decir, mayor que cualquier otro del conjunto. La triangulación correspondiente a dicho vector es la triangulación de Delaunay.

Pero lo que interesa de la triangulación en la aplicación realizada, es además de comprender que es la triangulación, es la propiedad que tiene toda triangulación que dice que todos las posibles triangulaciones sobre un mismo conjunto de puntos en el plano cuenta necesariamente con el mismo número de triángulos, además se tendrá que tener en cuenta que las aristas no podrán cruzarse entre sí. Pues bien esta propiedad de la triangulación se basará en la fórmula de Euler:

V -- E + F=2

Donde, V es el número de vértices, E es el número de lados, F el número de caras. Aunque se usará una variación de esta fórmula:

num_triangulos = (2*num_total_puntos)--2--lados_cierre_convexo

Cierre Convexo.

Una de las partes más complicadas de esta aplicación será conseguir el cierre convexo de la nube de puntos. A partir de este polígono se aplicará la fórmula antes descrita para saber el máximo número de triángulos que se pueden realizar en una nube de puntos y que significará el final de cualquiera de los tres juegos que se implementan en esta aplicación.

Hay muchos métodos para el calculo del cierre convexo, ya sea para dos, tres, o más dimensiones. Los más conocidos algoritmos son:

• Algoritmo de búsqueda de puntos extremos. O(n⁴).

• Algoritmo de búsqueda de aristas. O(n³).

• Algoritmo de Jarvis March. O(nh).

• Algoritmo Quick-hull. O(n log n).

• Algoritmo Scan de Graham. O(n log n).

Manual de usuario.

La aplicación contiene tres juegos basados en la triangulación de una nube de puntos. Los juegos comienzan con una pantalla llena de puntos, los jugadores deberán realizar triángulos uniendo los puntos , de dos en dos, que aparecen en la pantalla. Pasemos a describir de una manera mas exacta tanto la finalidad como las reglas de dichos juegos, así como otros detalles del mismo.

Finalidad:

Reglas:

 1.- El jugador al que le toque el turno de jugar tendrá que realizar una línea uniendo dos puntos de la pantalla (pulsando con el ratón sobre cada uno de los puntos que se desea unir). Para que dicha línea sea aceptada como válida no se podrá cruzar con otra línea o pasar por encima de otro punto.

 2.- Un  triangulo puntuable es aquel que no contenga ni puntos ni líneas ni otros triángulos.

 3.- Estos juegos lo jugarán dos jugadores que se irán alternando según  realicen líneas. Cuando uno de los dos jugadores realiza un triangulo puntuable vuelve a jugar (esta regla no se cumple en el tercer juego).

Otros datos:

Además de poder elegir que tipo de juego se quiere jugar, el usuario o usuarios podrán elegir el número de jugadores que van a jugar, dos jugadores, un jugador (el usuario contra el ordenador) y, por último, Simulador (el ordenador contra el ordenador).

En el caso de que el usuario elija "un jugador" o "simulador" podrá elegir también el nivel en el que jugará el ordenador ( 0 -> fácil, 1-> difícil).

Por último, el usuario podrá elegir el número de puntos que van a aparecer en pantalla.

Juego

Pulsando el siguiente botón se accederá a la aplicación de este trabajo fin de carrera (debe ejecutarse con Explorer):