PackingCircles
            

Proyecto Fin de Carrera:

Título: "Estudio de crecimiento de círculos en un recinto acotado".

Autor: Enrique Bañales Martínez. 

Tutor: Manuel Abellanas Oar.

Objetivos y Resultados

El proyecto presente se centra en temas relativos a la Geometría computacional, esta rama de la matemática se ocupa de dar soluciones algorítmicas a problemas geométricos. Para ser más exactos podríamos definir dicha ciencia como el estudio sistemático de algoritmos y estructuras de datos sobre elementos geométricos con una fijación especial en la búsqueda de algoritmos asintoticamente rápidos.

Para llegar a elaborar soluciones algorítmicas eficientes para problemas de naturaleza geométrica es necesario tener en cuenta dos factores:

• Primero, es necesario comprender las propiedades geométricas del problema, para poder aprovecharlas en la elaboración del algoritmo.

• Segundo, es necesario conocer las técnicas algorítmicas apropiadas para resolver eficientemente el problema y también poder usar las estructuras de datos necesarias para que ese algoritmo pueda funcionar de forma eficiente.

La Geometría computacional ha sido aplicada para solucionar problemas prácticos que se han planteado en areas como la robótica, la graficación por computador, CAD/CAM y los sistemas de información geográfica.

En este proyecto se pretende elaborar una simulación del crecimiento de círculos en un recinto. Movimiento que se ve influenciado por los choques que se producen entre los distintos círculos y las paredes del recinto.

Dicha simulación debe llegar en algunos casos al punto de bloqueo, en el que los círculos ya no pueden desplazarse ni crecer más al estar limitados por un recinto acotado, dicho recinto debe tener forma rectangular, aunque sus dimensiones pueden variar para realizar distintas simulaciones.

Una vez que la simulación llega a la situación de bloqueo se muestra el diagrama de Voronoi y la triangulación de Delaunay sobre una nube de puntos cuyos elementos son los centros de los círculos en su posición final, es decir, la que han alcanzado al final de la simulación.

El diagrama de Voronoi de un conjunto de puntos corresponde a la solución del problema de la oficina de correos, es decir, dados unos puntos de servicio situados en un área determinada, poder conocer cual de esos puntos de servicio es el más cercano a un punto cualquiera de ese área. Matemáticamente y dado un conjunto de puntos P={p₁,p₂,...,p_n} podemos definir el diagrama de Voronoi como la subdivisión del plano en n celdas, una correspondiente a cada punto de P, en la que se cumple que:

• Un punto q está contenido en la celda correspondiente a p_i si y sólo si distancia(q,p_i)<distancia(q, p_j) para cualquier punto p_j de P distinto de p_i.

La triangulación de Delaunay, la cual también se establece sobre un conjunto de puntos P, corresponde a una de las muchas triangulaciones de un conjunto de puntos con la particularidad de que la de Delaunay cumple que maximiza el valor del mínimo ángulo de cada triángulo qué compone la triangulación.

Siendo ésta la definición de la triangulación de Delaunay y habiendo visto la definición del diagrama de Voronoi se ha comprobado que una vez conseguido uno de ellos tenemos el otro, esto es, son problemas duales . Por lo que al desarrollar el proyecto, una vez obtenida la triangulación de Delaunay, ésta se utilizará para obtener el diagrama de Voronoi.

Una de las aplicaciones del mundo real en el que se puede usar la aplicación construída es el establecimiento de centrales de telefonía móvil, centrales que tienen que estar alejadas entre sí una distancia mínima (el radio del círculo) para no provocar interferencias entre ellas, el programa las situaría de manera que no interfiriesen entre ellas.

Otro problema en el que podría ayudar sería el problema de extraer "n" láminas círculares y de igual radio de una lámina rectangular de un material usado en la construcción, por ejemplo.

En definitiva el proyecto pretende llegar a construir una herramienta que ayude en el estudio del empaquetamiento de círculos en superficies rectangulares y cuadradas, proporcionando una simulación lo más aproximada posible al resultado final qué se obtendría intentando empaquetar círculos en recintos cerrados.