Calificación:
  • 0 voto(s) - 0 Media
  • 1
  • 2
  • 3
  • 4
  • 5

[-]
Etiquetas
voronoi y delaunay

Delaunay y Voronoi
#1
http://www.kirainet.com/delaunay-y-voronoi/

Vamos a comentar intuitivamente uno de los algoritmos mas famosos y mas otiles de la geometria computacional usando un ejemplo practico. Aprenderemos a generar imagenes como esta:

[Imagen: voronoi.jpg]

Comenzamos la aventura. Imaginaros que tenemos una empresa de transporte con varias centrales de distribución, cada punto de la imagen representa uno de estos centros:

[Imagen: voronoi1.jpg]

Ahora imaginaros que debemos determinar las zona que debe cubrir cada central de distribución de forma que tengamos que viajar lo minimo posible. Es decir, debemos determinar las zonas del plano que estan mas cercanas a cada punto.

Para calcular estas zonas hay que seguir una serie de pasos. Primero debemos aplicar el algoritmo de Delaunay, que consiste en trazar triangulos entre los vartices con ciertas restricciones que ahora veremos. Veamos una posible triangulación:

[Imagen: voronoi2.jpg]

Esta es una forma de triangular, pero para nuestro propósito no es valida. Debemos conseguir una triangulación de forma que Cualquier circunferencia trazada entre los 3 vartices de cada triangulo no tenga ningon otro punto dentro. Lo veremos mas claro con una imagen que demuestra que la triangulación anterior no era valida:

[Imagen: voronoi3.jpg]

¿Cómo solucionamos el problema? Pues probando diversas triangulaciones (Hay un matodo complicado de explicar que lo hace muy bien) hasta que no haya ninguna circunferencia que toque mas de 3 vartices. En nuestro caso solo tenemos que cambiar una arista:

[Imagen: voronoi4.jpg]

Fijaros que hemos cambiado un poco la triangulación y ahora al trazar la circunferencia ya no tenemos ningon otro vartice interior. Si hacemos lo mismo con el resto de triangulos vemos que hemos conseguido que no tengan otros vartices dentro, en este momento hemos conseguido la Triangulación de Delaunay a partir de los vartices/centrales de distribución iniciales. En la siguiente imagen trazamos todas las circunferencias posibles, fijaros que ninguna toca mas de 3 vartices.

[Imagen: voronoi5.jpg]

Pufff, un poco lioso pero lo que queda es cuesta abajo. A continuación debemos calcular las regiones mas cercanas a cada punto (A estas regiones las llamaremos Regiones de Voronoi). Para ello nos apoyaremos en la Triangulación de Delaunay que ya hemos calculado. Marcamos el punto central de cada circunferencia y trazamos Perpendiculares a las aristas de los triangulos. Vamos a verlo con dos de los circulos para no liar (Los puntos amarillos son los centros de las circunferencias y las lineas naranjas son perpendiculares a las aristas de los triangulos):

[Imagen: voronoi6.jpg]

Si seguimos aplicando el mismo matodo (y eliminamos del dibujo los circulos para no liar) obtendremos lo siguiente:

[Imagen: voronoi7.jpg]

Si ademas eliminamos la Triangulación de Delaunay, tendremos la imagen definitiva donde se definen las zonas mas cercanas a cada centro de distribución:

[Imagen: voronoi8.jpg]

Por ejemplo, la zona coloreada de verde es la Región de Voronoi del punto A. Esto quiere decir que todo lo que esta pintado de verde esta mas cerca de A que de cualquier otro punto del dibujo. Lo podais comprobar con una regla si no os convenzo [Imagen: icon_wink.gif]

[Imagen: voronoi9.jpg]

Si habais llegado hasta aqui, tenais premio: Un applet donde haciendo clicks podais ir colocando las sedes de vuestra empresa y vais viendo en tiempo real la triangulación de Delaunay y las regiones de Voronoi. Tambian podais generar muchos puntos dandole al botón Generar, con el que conseguirais una imagen similar a la mostrada al inicio de este articulo. A los programadores os pongo el código fuente por si quieren trastear algo, os aviso que esta muy poco documentado.

Resumiendo, en geometria computacional las regiones de Voronoi son las zonas del plano mas cercanas a un conjunto dado de puntos. Esto a nivel practico lo utilizan muchas empresas para definir sus zonas de cobertura. Por ejemplo, McDonalds lo utiliza para decidir donde tiene que poner una nueva sede. Tambian se utiliza en planes de prevención de riesgos para saber a que zonas afectaria un escape de una central nuclear.
Tambian se utiliza en aplicaciones mas artisticas, como en la primera imagen de este articulo, la creación de cristaleras etc. Tambian podais generar vuestras regiones de voronoi utilizando Photoshop: Filtro -> Textura ->Vidriera . Para aplicar ese filtro Photoshop internamente realizar la Triangulación de Delaunay que hemos aprendido y posteriormente calcula las Regiones de Voronoi. Todos a crear Vidrieras y si no os queda algo claro preguntad [Imagen: icon_smile.gif]

LINKS UTILES:

http://www.dma.fi.upm.es/mabellanas/ante...tenido.htm
http://www.comp.lancs.ac.uk/~kristof/res...s/voronoi/
http://www.voronoi.com/cgi-bin/display.v...cat=Theory
http://www.geom.uiuc.edu/software/cglist/ch.html

Responder
#2
Como siempre BRILLANTE !!!

:plasplas:

Un saludo.
Responder


Salto de foro:


Usuarios navegando en este tema: 1 invitado(s)