Generación de diagramas de Voronoi con el algoritmo de Fortune

Cómo generar diagramas de Voronoi

• ¿Qué es un diagrama de Voronoi?

  • Un diagrama de Voronoi es una forma de dividir el plano en varias regiones, y se usa principalmente para generar mapas de manera procedural.
  • Se eligen varios puntos en el plano, llamados "sitios", y la región correspondiente a cada sitio contiene todos los puntos más cercanos a ese sitio.
  • Los límites de cada región están formados por puntos que están a la misma distancia de dos sitios. Los puntos que están a la misma distancia de tres sitios se llaman "vértices de Voronoi".

• Algoritmo de Fortune

  • El algoritmo de Fortune es un método para generar el diagrama usando una línea que hace un "barrido" del plano de izquierda a derecha.
  • Cuando la línea de barrido encuentra un sitio, se genera una "burbuja" (un arco parabólico) a su alrededor, y esa burbuja crece a medida que la línea de barrido se aleja.
  • Cuando los arcos de dos sitios chocan, ese punto de colisión se convierte en el límite entre celdas.
  • El límite de todas las burbujas activas se llama "línea de playa".

• Glosario de términos

  • Sitio: un punto bidimensional que determina la forma del diagrama de Voronoi.
  • Línea de barrido: una línea vertical que cruza la región y procesa cada evento de la cola de eventos.
  • Línea de playa: una línea compuesta por varios arcos, donde se agregan o eliminan arcos a medida que se procesan eventos.
  • Punto de intersección: el punto donde se encuentran dos arcos de la línea de playa, y está a la misma distancia de los sitios relacionados.
  • Cola de eventos: donde se almacenan los eventos de sitio y de círculo, ordenados por coordenada x ascendente.
  • Evento de sitio: uno de los dos tipos de evento en la cola de eventos, definido por las coordenadas del sitio correspondiente.
  • Evento de círculo: el otro tipo de evento en la cola, definido por tres arcos sobre la circunferencia de un círculo.
  • Vértice de Voronoi: un punto que está a la misma distancia de tres sitios y forma una esquina de una celda.
  • Límite equidistante: una línea que está a la misma distancia de dos sitios.
  • Límite incompleto: una línea con un extremo fijo y otro definido por el punto de intersección de los focos de dos parábolas.

• Tangentes parabólicas

  • El concepto y las propiedades de la parábola son muy importantes en el algoritmo.
  • Una parábola se define por un punto focal y una línea recta (directriz).
  • Si se establecen los focos de dos sitios y se usa la línea de barrido como directriz, se puede encontrar la línea límite equidistante entre ambos sitios hallando el punto de intersección de las dos parábolas.

• Volviendo a la línea de playa

  • La línea de playa es el "límite" de todos los arcos en un punto dado de la línea de barrido.
  • Cada arco puede representarse mediante el punto focal de un sitio.
  • La línea de playa puede representarse como una secuencia simple de puntos.

• Se crea un nuevo arco cuando la línea de barrido encuentra un nuevo sitio

  • La línea de playa es una secuencia de puntos, y cada punto representa un sitio y un arco.
  • Cuando la línea de barrido encuentra un nuevo sitio, se crea un nuevo arco y se inserta en la secuencia.

• Límites que se cruzan y circunferencia circunscrita

  • Cuando tres sitios están sobre la circunferencia de un círculo, el centro del círculo está a la misma distancia de los tres puntos.
  • El centro de la circunferencia circunscrita se convierte en un vértice de Voronoi.

• Límites incompletos

  • Un límite incompleto tiene un extremo fijo y el otro es la intersección de dos arcos.
  • Cuando dos límites incompletos chocan, se genera un vértice de Voronoi y los límites incompletos se convierten en semilímites.

• Solo los círculos en sentido antihorario generan eventos de círculo

  • Solo se genera un evento de círculo cuando tres arcos se leen en sentido antihorario.

• Resumen

  • Dado un conjunto de sitios, todos los puntos de sitio se insertan en la cola como eventos de "sitio" y se ordenan por su valor x.
  • Mientras la cola no esté vacía, se extrae y procesa el siguiente evento.
  • Si es un evento de sitio, se agrega un nuevo arco a la línea de playa y se genera un límite incompleto.
  • Si es un evento de círculo, se agrega un vértice de Voronoi y se elimina un arco de la línea de playa.