¿Está Voronoi? Que se ponga

Ilustración: | Raquel Garcia Ulldemolins

Mentiría si dijera que me esperaba la buena acogida que mi anterior entrada sobre los diagramas de Voronoi ha recibido. Cosa que por otra parte viene a corroborar lo que he pensado desde 1995, año que en que la descubrí: ¡la Geometría Computacional mola! Oye, que hasta hemos ganado en la IX edición del Carnaval de Matemáticas.

A eso vamos, pues.

Por si alguno de vosotros no la ha leído y no sabe qué es un diagrama de Voronoi, aparte de recomendar la citada entrada, recordaré que en el caso de un conjunto finito de puntos del plano, el diagrama de Voronoi de los mismos es la división del plano en regiones, tantas como puntos tengamos, de tal forma que a cada uno ellos le asignamos la región formada por aquellos puntos que están más cercanos a él que ningún otro de los originales.

Ya mencionábamos en aquella entrada la utilidad de este tipo de diagramas, por ejemplo, pasa atribuir la propiedad de un caramelo en el patio de los Lunnis.

En el siguiente vídeo podéis ver cómo se va calculando el diagrama de Voronoi de personas que se están moviendo sobre una plataforma.

Imagen de previsualización de YouTube

Precioso, ¿verdad?

Uno no pararía nunca de encontrar aplicaciones de esta estructura, hasta para crear fractales se puede utilizar.

También existe el juego de Voronoi en el que tenéis que conseguir mayor región de influencia para vosotros que vuestro contrincante, colocando inteligentemente vuestros puntos.

Hasta una aplicación para iPad e iPhone en la que,  con tus dedos, dibujas sobre la pantalla, y el diagrama de Voronoi los puntos que describen esa trayectoria de tus dedos produce algo tan bello como esto:

Imagen de previsualización de YouTube

También en la serie Numb3rs se habla de ellos…

Imagen de previsualización de YouTube

Pero si bien ya dedicamos la entrada anterior a cantar las bondades y utilidades de dicho diagrama en distintas áreas, en ésta que estáis leyendo vamos a hablar sobre su construcción. Que se ponga Voronoi y nos explique cómo se calcula el diagrama, ¿no?

Antes de meternos en faena, dejadme que me pare un poco en contaros cómo algunos usuarios de Twitter encontraron  distintas interpretaciones del diagrama, más… poéticas.

Eso sí, si eres estudiante de arquitectura. Igual deberías pensártelo antes de seguir leyendo esta entrada, porque hay ya algunos profesores que están un poco mosqueados con el tema… La que avisa…

Pues nada, al lío.  ¿Cómo se construye el diagrama de Voronoi de un conjunto de puntos en el plano?

Vamos a ir poco a poco, para no agobiarnos.

Si tenemos sólo dos puntos, que en un derroche de originalidad podríamos llamar A y B, para calcular las regiones de Voronoi de éstos, que llamaremos, respectivamente, Vor(A) y Vor(B), sólo hay que dibujar una línea.

Esa línea o recta, es lo que conocemos como mediatriz entre A y B, y se calcula sin más que trazar el segmento que une A con , y por el punto medio de dicho segmento, trazar la recta perpendicular al mismo.

Pues, casi sin despeinarnos, ya hemos superado este escollo.

Vamos a ver qué pasa con 3 puntos,  a los que llamaremos A, B y C.  Comenzamos calculando la  región de Voronoi de A, Vor(A), primero delimitando su territorio frente a su vecino B.

Ahora, delimitamos su territorio frente a C

Y tenemos la región de Voronoi de A, en color violeta en la siguiente figura.

Ahora le toca a B, delimitando su territorio frente a A (en amarillo) y a C (en naranja claro)

Coloreamos en verde Vor(B)

Y, ¡tachán!

Antes de seguir, vamos a fijarnos en este dibujo. Porque el vértice en el que se cortan las tres fronteras de Vor(A), Vor(B) y Vor(C) no es un punto cualquiera. no.  Es el centro de la única circunferencia que pasa por A, B y C. Es más, es el círculo que contiene al triángulo definido por esos tres puntos.

Este hecho, el de que el vértice de Voronoi defina un círculo vacío para tres puntos cercanos, es una propiedad muy, muy, muy interesante que se usa para optimizar modelado de terrenos mediante el uso de triangulaciones. Pero, de Delaunay y sus triangulaciones, ya hablaremos otro día, que pierdo el hilo.

¿Y si tenemos 4 puntos?

Muy bien. Efectivamente. Repetimos el proceso de nuevo: para cada uno de los puntos, calculamos los 3 semiplanos que le pertenecen a él y no a ninguno de los otros 3 y calculamos la intersección de esos  3 semiplanos.  Oye, y sale.  La cosa es que el diagrama de Voronoi vamos a querer calcularlo con el ordenador, y no para 4 puntos, sino, posiblemente para miles.

¿Y si tengo 1000 puntos? ¿Tengo que calcular 1000 veces la intersección de 999 semiplanos? Ya, ya, lo  hace la máquina, pero estará haciendo un montón de cálculos innecesarios, porque de los 999 puntos, serán muy pocos los que compartan frontera en su región de Voronoi con él; de esos 999 semiplanos la mayoría no intervendrán en la región de Voronoi del punto procesado en ese momento.  Estamos haciendo demasiados cálculos, y estamos en crisis… Bromas aparte, buscamos diseño de algoritmos rápidos y eficientes, óptimos.

Vamos a ver si podemos recortar algo y hacerlo más eficientemente.

Hay bastantes algoritmos óptimos (no se pueden mejorar los tiempos de ejecución) para el cálculo del diagrama de Voronoi, os voy a contar uno de ellos, que me gusta mucho.

Se basa en el paradigma de Divide y Vencerás, divide et vinces que diría Julio  César, si pudiera el buen hombre. Pues sí, es una técnica utilizada en el ejército, en la política…y que os recomiendo en la vida en general. Si os veis muy agobiados por un problema de la vida en general o de Matemáticas en particular, tratad de resolver una mitad y luego la otra. ¿Qué la mitad no se deja? Pues la dividimos otra vez y vamos por los cuartos. Y si no, por los octavos, y así, hasta que encontremos un problema abordable y lo resolvemos. Después sólo habrá que pegar los resultados.

Y que, ¡ojo!, no lo digo yo sola, que el mismísimo Descartes lo proponía en su Discurso del método:

Dividir cada una de las dificultades que examinare, en tantas partes fuere posible y en cuantas requiriese su mejor solución.

Y hasta Beppo, al amigo de Momo:

Nunca se ha de pensar en toda la calle de una vez…Sólo hay que pensar en el paso siguiente, en la inspiración siguiente, en la siguiente barrida.

Bueno, que me enrollo. Vamos a ver cómo se pegan dos diagramas de Voronoi y si lo entendemos, fin. Porque cuando tengamos un conjunto, yo que sé, de 50 puntos, lo dividimos en trozos de 2 o 3 puntos, que a ésos le calculamos el diagrama de una patada y luego sólo tendremos que pegar los diagramitas obtenidos para tener el diagrama entero. Eso sí, para dividir el conjunto original en conjuntos de 2 o 3 puntos, vamos a usar restas paralelas de separación, por ejemplo verticales.

Supongamos que tenemos un conjunto de 10 puntos y que ya hemos calculado el diagrama de 6 de ellos por una lado (pegando 2 diagramas de 3) y el de los otros 4, por otro (pegando 2 diagramas de 2). Vamos a pintar esos dos subconjuntos diferentes para facilitar la escritura, y como soy de Sevilla, de verde y rojo, los eternos colores rivales de por aquí.

Para pegar estos dos diagramas, el rojo y el verde,  supongamos que son soldados de dos ejércitos muy, muy enemigos. Un observador neutral quiere atravesar la zona de norte a sur, (que ya hay que tener ganas, sí) y desea hacerlo sin herir susceptibilidades. Para ello, debe pasar siempre a la misma distancia de un soldado rojo que de un soldado verde, claro está.

Pues si viene desde el norte, desde mucho antes de la zona en conflicto, es fácil comprobar, que los dos primeros soldados que lo van a controlar, para que no se acerque más al enemigo que a él mismo, serán  2 puntos, uno rojo y uno verde, de las envolventes convexas roja y verdes, respectivamente, de tal forma que la recta que los une deja a los 10 puntos en el mismo semiplano. Vamos, los dos que están señalados en la figura de la arriba.

Pues, vamos, el observador llegará por el norte caminando sobre la ruta azul, que no es más que la mediatriz entre los dos soldados que lo están vigilando, para que nadie se mosquee.

Cuando el observador se encuentra con una frontera roja, como ocurre en la figura inmediatamente superior, el soldado rojo que lo vigilaba, le cede el puesto a un nuevo soldado de los suyos. ¿A cuál?   Pues, evidentemente al dueño de la nueva región roja en la que ha entrado el caminante.  Entonces, este cambiará su trayectoria a la mediatriz entre el soldado verde original y el nuevo soldado rojo.

Lo siguiente que ha encontrado el observador ha sido una frontera verde (figura anterior), por lo tanto, relevo en las filas verdes. Y el paseante caminará sobre una nueva mediatriz, la del punto rojo que traía y el nuevo verde.

De nuevo llegamos a una frontera roja: cambio de soldado rojo y cambio de mediatriz.

¿Llegamos a una frontera verde? Pues cambiamos de vigilante verde y caminamos por la mediatriz entre él y el rojo que nos estaba vigilando.

Y así, caminando por la ruta en azul, el observador sale sano y salvo porque en ningún momento se ha acercado más a un olor que al otro.

Ahora viene lo bueno.

Si eliminamos las líneas verdes que se han quedado a la derecha del camino azul, y las líneas rojas que se han quedado la derecha, ¿qué es lo que nos queda?

¡Sí, sí, sí! ¡El diagrama de Voronoi de los 10 puntos!

Alucinante, ¿no? Siempre  digo a mis estudiantes de Geometría Computacional que si no alucinan con esto es porque no les queda sangre en el cuerpo. Me miran raro.

Pues bien, este método basado en el Divide y Vencerás es óptimo para el cálculo para el cálculo del Diagrama de Voronoi, mucho más que el de calcular la intersección de semiplanos. Pero no es el único. Hay muchos más, pero no podemos contarlos hoy todos.

Uno que me parece especialmente bello también es debido a Fortune y es conocido como la Línea de  Playa. En pocas palabras, lo que hace es un barrido con una recta, vertical por ejemplo, actualizando la mediatriz entre dicha recta y los puntos que se va encontrando. La mediatriz entre un punto y una recta es una parábola, sí. Si tenemos que dividir el plano entre los puntos que están más cerca a una recta y los que están más cerca a un punto exterior a la misma, lo que nos queda es algo así.

Si queréis ver cómo funciona, os dejo este enlace con una aplicación que os lo muestra, sólo tenéis que añadir con el ratón los puntos que queráis, y a disfrutar.

Una última curiosidad.  Mi amigo y colega José Cáceres pidió a un estudiante suyo que calculara el diagrama de Voronoi de las capitales de provincia españolas en la península, lo hicieron.

Click para ampliar

Como podéis ver en el mapa de la derecha, no difieren tanto ¿Significa eso que las capitales de provincia están bien elegidas desde el punto de vista geométrico?

Termino diciendo que ésta ha sido una manera informal de hablar de algoritmos que calculan el diagrama, sin rigor, sólo para divulgación, ¡no para un examen de Geometría Computacional! Si quieres algo más, no dudes en ponerte en contacto conmigo, porque Voronoi… está sin cobertura ;)

———————-
Esta entrada participa en la Edición 2.10 del Carnaval de Matemáticas, cuyo anfitrión es el blog Resistencia Numantina

45 Comentarios

Participa Suscríbete

BioSamu_

Debo decir que el anterior post sobre los espacios de Voronoi fue muy revelador para mi mente, que se pasa el tiempo tratando de buscar patrones intuitivos. No tenía ni idea sobre el asunto y rápidamente acudí a contarle a mi hermana, que es matemática, lo que me había fascinado la idea.

A lo mejor meo fuera del tiesto, pero pensé que esto es claramente aplicable al comportamiento social, si pudiéramos representar geométricamente las necesidades y libertades individuales; sería otra forma de representar la metáfora del cuarto de baño, de Asimov.

ClaraClara

¡Chulísimo! Creo que voy a copiar la idea de José Cáceres pero para hacer el diagrama de Voronoi para los Ikeas, porque siempre dudo de cuál es el que me pilla más cerca.
Podría ser interesante para los aeropuertos, pero ¿se pueden asignar pesos, en función del número de aviones, por ejemplo que hagan más grande una zona de influencia? Porque desde Agoncillo sale menos de un avión al día y no se si es merecedor de su propia zona de Voronoi.
Genial como siempre Clara.

ManuelManuel

En algun momento -sin saber que era Voronoi- utilizamos ese concepto en un algoritmo de generacion de horarios… Y, para mejorarlo aun mas, le asignamos “pesos” a cada curso, en funcion a sus creditos. GENIAL entrada! :)

Clara Grima

Sí, existen muchos trabajos sobre Weighted Voronoi diagram, que son con pesos para situaciones como las que planteas. Si te interesa, puedo buscarte algunas referencias.

Muchas gracia, tocaya :)

SaraySaray

Absolutamente genial… pasar de la diversión al asombro, y del asombro a la comprensión resulta infinitamente gratificante.

VictorVictor

Excelente artículo Clara (disculpa que te tutee). Como físico de formación, ingeniero de profesión pero matemático de corazón, es agradable ver esta clase de artículos tan bien explicados. Ojalá hubiera tenido profesores que explicaran tan bien la ciencia. Lo dicho, enhorabuena!

Omegan

Sublime ¿Podrias hablar un dia sobre diagramas de Voronoi ponderados?

Me refiero a tomar en cuenta irregularidades del terreno (rios, montañas…) o importancia de uno de los puntos.

Gracias

Clara Grima

Muchas gracias, Omegan.

Pues sí, hay otros diagrams de Voronoi, en otras dimensiones, ponderados, con otros objetos geométricos que no son puntos (segmentos, polígonos, esperas), incluso diagramas de Voronoi que asocian la región del plano de los puntos más alejados de ti que de nadie (con sus aplicaciones en optimización en la localización de servicios deseables)….

Me lo pienso ;)

Robespain

Hola Clara.
Gracias por los artículos. Yo fui quien envió tu entrada de Dios, π y el infinito a Meneame, aunque tampoco tiene mucho merito, por que si no hubiese sido yo la habria mandado otro. Eres una crack, escribes muy bien y necesitamos mas personas como tu. Gracias por seguir compartiendo lo que se te pasa por esa pedazo de cabeza y ese pedazo de corazón que tienes.

robespain

¡A mi también me ha emocionado tu respuesta!
Es de las cosas mas bonitas que me han llamado en mucho tiempo. Aunque realmente quien hizo que la mariposa batiera sus alas, fue el usuario Milhaud:
http://www.meneame.net/c/7393467
Si el no hubiese escrito este comentario, yo no habria leido tu articulo ni lo hubiese mandado.
Acabo de leer el enlace que me pones, y recordarte que todo el merito es tuyo y solo tuyo. El mundo se abre camino a quien hace las cosas con el corazón.

ZarzaZarza

Muy divertido. Todo está en dos dimensiones pero si la mediatriz fuese el espejito mágico. ¿Qué imágenes encontraríamos en ese mundo 3D? .

saxsurfersaxsurfer

Como a otros primerizos, el tema me ha dejado fascinado, en gran parte por la brillantez y gran aliento pedagógico de tus explicaciones, Clara. Muchas gracias.
Hablando de la aplicación de Voronoi a la división provincial, los pequeños desajustes con la división legal tienen su impacto en nuestras vidas: en España muchos servicios avanzados (especialidades sanitarias, enseñanza superior, inspección tributaria, etc.) residen en la capital de la provincia. Los habitantes de los pueblos que no están en la “provincia voronoi” que les correspondería siempre protestan porque tienen que emplear más tiempo para resolver sus problemas. Propongo un reforma de la ley para cambiar los límites a la Voronoi.

Clara Grima

Muchas gracias, Saxsurfer, de verdad :’)

No está la cosa para proponer leyes que mejoren el acceso a servicios sociales, sobre todo si son públicos, pero podemos intentarlo ;)

Lo malo es que decidan eliminar ‘puntos’ para que las regiones de influencia sean aún más grandes…Oh, wait… :(

Juanola

No sé si leerás este comentario pero mis más sinceras felicitaciones, tanto por este artículo como por el anterior. Como informático que soy me encanta leer las aplicaciones que tienen las cosas (por ejemplo me fascinó el uso de voronoi para el cálculo del camino de un robot en una habitación!!!) pero lo que más me gusta de ambos articulos es que una asignatura tan complicada como las matemáticas (debido a la manera en que se la enseña en los colegios) se vuelve tan interesantisima con cosas como estas. Ojalá en todas las clases de matemáticas de todos los colegios se explicase de esta manera, habría muchos menos niños desinteresados por las matemáticas. Enhorabuena de nuevo!!!

Clara Grima

Muchas gracias, Juanola, me alegro de que te guste.

Evidentemente hay malos maestros, como hay malos profesionales en cualquier actividad. Pero tengo que decir, que es más fácil explicar los diagramas de Voronoi que enseñar a leer o restar ¡con llevadas! Pero hay que intentarlo, es verdad.

XurxoXurxo

Genial de nuevo, Clara. ¡Me ha encantado! Y me he puesto a toquetear la pantalla con la app “Bubble Harp”. Gracias :)

adfasdadfasd

No, no lo están porque el trabajo necesario para desplazarse de un punto a otro de una región de Voronoi no es dependiente de su distancia euclidea.

offler

Sorprendente el parecido de las provincias con las areas de Voronoi

Es más, una de las mayores diferencias que veo es en Aragón con Catalunya, y eso explicaría la zona que se conoce como la Franja, que pertenece a Araqgón pero hablan catalán

GuibuuGuibuu

Me parece un diagrama estupendo, sencillo de entender, con muchas utilidades prácticas, y muy vistoso.

Me gustaría jugar con él (sin tener que generarlos línea a línea) en programas como AutoCAD o SketchUp, pero casi no he encontrado ningún plugin para estos programas, ni una forma cómoda de exportar los resultados de otras aplicaciones como applets en Java para juguetear en el navegador.

¿Alguna idea? Ya me gustaría tener la destreza necesaria para escribir un script para estos programas yo mismo…

JagudoJagudo

Lo que decíais antes de los diagramas de Voronoi con pesos se parece mucho al cálculo de cubiertas en edificios, en los que los pesos equivaldrían a las distintas pendientes que se quieran utilizar.

vendettavendetta

Plas plas plas… Espectacular continuación del artículo original, da gusto leer una expliación tan clara y concisa. ¿Habrá tercera (y cuarta, y quinta…) parte? ¡Espero que sí!

Otra aplicación de este método, que me toca de cerca por la parte profesional, consiste identificar zonas del cielo libres de estrellas brillantes. Esto es vital para poder calibrar imágenes astronómicas tomadas con cámaras de gran campo. Unos colegas han diseñado una aplicación para el Observatorio Virtual que, mediante la triangulación de Delaunay, localiza estas zonas a partir de un catálogo con las coordenadas y luminosidades de miles de estrellas:

http://sdc.cab.inta-csic.es/tesela/index.jsp

EduEdu

Muchas gracias Clara, a cual de los dos artículos mejor.
Y yo intentando que mis hijos dejen de mirar a las matemáticas como a un ogro… Qué envidia (sana)!

cristiancristian

Lo estaba leyendo en el readitlater pero he tenido que venir hasta el post porque esto se merece una felicitación. Me han encantado los dos artículos, en ambos es como si me lo explicase mi madre, y se agradece un montón =) Enhorabuena!

JokinJokin

No estoy muy al dia sobre Vornoi pero leido esto me gustaria saber que aplicacion practica se podria dar al futbol en cuanto ocupacion racional del terreno de juego por los futbolistas(puntos) durante un partido en las distintas situaciones que se presentan. ¿Crees que Bielsa utiliza a Voronoi en sus estrategias y tacticas?. Que alguien me diga algo por favor. Saludos

Marian JiménezMarian Jiménez

Nunca entendí ,as matemáticas….intuía que debía haber alguna forma hacerlas cercanas….y tullo haces tan fácil!!!tengo un ex- marido informático cuyos robots viajan de un lado a otro del mundo sin chocar …..claro! Hoy lo entendí…voronoi esta de guardia urbano y les avisa cuando van a chocar…
Gracias por enseñarme que las matemáticas están ,también,a mi alcance.

KarlosnakeKarlosnake

Magnífico, sensacional, apasionante…¡¡¡y hablamos de matemáticas!!!

Yo sigo dándole vueltas a lo de las provincias XD, ¿alguien sabe si se eligieron así por ese motivo? conscientemente digo.

JavierJavier

Hubo una época en la que quería figurar en todos lados, ahora es algo a lo que no soy muy dado. Las caricias del tiempo me han hecho valorar más la intimidad que el figurar, incluso lo que a mis alumnos les escribo, con el nombre del departamento lo suscribo.

Pero tras escuchar hablar sobre diagramas de Voronoi, y contenido relacionados con familiar apasionamiento, mis dedos no se han podido contener para expresar mi agradecimiento.

Cuando ya te has quedado muchas veces perplejo, tras mostrar la belleza de lo que enseñas y tus oyentes ni siquiera se inmutan, empiezas a aceptar que la enseñanza de Las Ciencias es un mundo bastante complejo.

La simpatía y la empatía, además del apasionamiento de lo que con tus palabras exponías han hecho reverdecer el paisaje otoñal, para que con renovada savia la próxima cuatrimestral la aborde con actitud primaveral.

Gracias Clara, nunca pensé, que escuchando a una colega me reciclara.

13 Trackbacks

Información Bitacoras.com…

Valora en Bitacoras.com: Ilustración: | Raquel Garcia Ulldemolins Mentiría si dijera que me esperaba la buena acogida que mi anterior entrada sobre los diagramas de Voronoi ha recibido. Cosa que por otra parte viene a corroborar lo que he pensado d……

[...] ¿Hay alguien ahí? ¿Sí? Sigo entonces… No quiero que quedéis Confundidos por la realidad o que en lugar de estar concentrados en mi entrada, estéis pensando ¿Cómo viajar a Marte? o en un laboratorio Moviendo objetos con la mente mediante un brazo robótico… Y todo esto sin  tener a mano las Instrucciones para hacer un cuerpo humano y/o utilizando Fuentes de energía más de ciencia que de ficción. ¿Está Voronoi? Que se ponga… [...]

Deja un comentario

Tu email nunca será mostrado o compartido. No olvides rellenar los campos obligatorios.

Obligatorio
Obligatorio

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <p> <q cite=""> <strike> <strong>