PackingCircles
             

Final Project:

Title: "Estudio de crecimiento de círculos en un recinto acotado". (Notes about Packing Circles in a closed enclosure)

Author: Enrique Bañales Martínez. 

Tutor: Manuel Abellanas Oar.

Targets and Results

The present project  is about Computational Geometry, this branch of Mathematic science is about to find algorithmical solutions to geometric problems. In more accurate terms, Computational Geometry can be defined as the sistematic study  of algorithms and data structures applied over geometric elements with a special focus in searching asintotic fast algorithms.

For developing efficient algorithmic solutions in order to solve geometric nature problems, we need to consider two issues:

• First, we need to know the geometric properties of the problem, in order to exploit them for the development of our algorithm.

• Second, we have to know the appropiated algorithm methods to solve  the problem in a efficient way, we also have to know about the data structure nedeed for that algorithm to work efficiently.

The Computational Geometry has been applied to solve practical problems that have been proposed in Robotics, Computer Graphics, CAD/CAM and Geographic Information Systems.

In this project we pretend to develop a simulation of the increase of circles in an enclosure until they reach a packing configuration. This simulation is set by the collisions between the circles themselves and between the circles and the enclosure.

This simulation will reach a blocking situacion (in the case that the enclosure is closed), when the circles didn't increase their radius because they are limited by the enclosure. This enclosure has rectangular form in many cases , although the user can resize it to make simulations in a square.

When the simulation is paused or has reached the blocking state, the user can see the Voronoi Diagram an the Delaunay Triangulation over a set of points whose elements are the circles centers.  

The Voronoi Diagram of a set of points is equal to the solution to the mail center problem, we have some service points in a set area and we have to find out what service point is nearer to any point  that belongs to the area. So being P={p₁,p₂,...,p_n} we can define the Voronoi Diagram as the plane subdivision in "n" sub-areas, one for each point belonging to P that complies with:

• One point q belongs to the sub-area of p_i if it's observed that distance(q,p_i)<distance(q, p_j) for any point p_j of P not equal to p_i.

The Delaunay Triangulation , which is defined in a set of points P, can be defined as one triangulation of a set of points which observes that it maximizes the  value of the minimum angle of every triangle of the triangulation.

Now that we have given the definition of the Delaunay Triangulation and we also have defined the Voronoi Diagram, we can say that it has been proved that starting from one of them we will obtain the other,that is, they are dual problems . So in this project first we achieve Delaunay Triangulation, and then starting from the Delaunay Triangulation we will obtain the Voronoi Diagram.

One of applications in which we can use the developed program is the establishment of mobile phone aerials, there must be a minimum distance between these ones to avoid interferences, the program will place them so there will not be interferences between them.

Another situation where this program can be useful is about extracting "n" equal round sheets from a rectangular sheet made of building material, for example.

In short, this project pretends to develop a tool for helping in the research of circle packing in rectangular and square areas, giving us an aproach as good as possible to the real solution of packing "n" circles in a rectangular area