Este artículo te da una guía paso a paso de cómo se pueden calcular las fronteras en un diagrama de Voronoi.

La geometría de las particiones de Voronoi

Una partición de Voronoi se hace al tomar un conjunto de sitios dispuestos en la pantalla y dibujar fronteras entre ellos, de tal manera que cada frontera esté exactamente a la mitad entre los sitios a cada lado de ella.

Dividir dos sitios

Vamos a empezar con dos sitios, A y B. Cada punto en la recta que los divide está a la misma distancia de A y de B. ¿Qué otras propiedades tiene esta recta?
Dos sitios y una frontera
Lo primero que podemos hacer es dibujar un segmento de recta de A a B. Como todos los puntos en la frontera están a la misma distancia de A y de B, la frontera va a cruzar start overline, A, B, end overline en el punto medio, M.
Puedes aprender más sobre puntos medios aquí.
Recta AB con el punto medio M marcado.
Ahora podemos escoger otro punto en la frontera, P, y hacer dos triángulos: triangle, A, M, P y triangle, B, M, P.
Frontera con el punto P marcado
El punto P está en la frontera así que sabemos que start overline, A, P, end overline, equals, start overline, B, P, end overline.
También sabemos que start overline, A, M, end overline, equals, start overline, B, M, end overline y que ambos triángulos comparten el lado start overline, M, P, end overline.
Como ambos triángulos comparten tres longitudes laterales, son triángulos semejantes. Puedes aprender más sobre triángulos semejantes aquí.
Como triangle, A, M, P y triangle, B, M, P son semejantes, sabemos que angle, A, M, P, equals, angle, B, M, P. Como ambos ángulos están en una línea recta (la recta A, B), sabemos que angle, A, M, P, plus, angle, B, M, P, equals, 180, degree. Entonces ambos ángulos deben ser de 90, degree.
Por lo tanto, la frontera entre A y B es la mediatriz de la recta A, B. Puedes aprender más sobre mediatrices aquí.

Dividir tres sitios

Así que sabemos que la frontera entre dos sitios es una mediatriz de la recta que une a esos dos sitios. ¿Cómo podemos usar esta información para encontrar la partición de Voronoi de estos tres sitios? Primero, vamos a empezar por dibujar rectas entre los sitios.
Triángulo ABC
Después vamos a encontrar los puntos medios de las aristas y a dibujar las mediatrices de cada arista.
Triángulo con mediatrices en cada arista.
Observa que las tres mediatrices se encuentran en un punto, V. Como cada mediatriz está a la misma distancia de dos sitios y V está sobre las tres, V debe estar a la misma distancia de los tres sitios. Por lo tanto, V es un vértice de nuestra partición de Voronoi. Podemos dibujar nuestras fronteras finales al empezar en este vértice y continuar por cada uno de los puntos medios.
Mediatrices que se encuentran en el punto V
La partición de Voronoi final

Preguntas

  1. ¿Cuál es el término para el punto V en relación al triangle, A, B, C?
    Ve la lección sobre mediatrices.
  2. ¿Bajo qué circunstancias las mediatrices no se van a intersecar?
    ¿Bajo qué circunstancias los puntos A, B y C no forman un triángulo?

El álgebra de las particiones de Voronoi

Ya que vimos algo de la geometría de una partición de Voronoi sencilla, vamos a usar álgebra para calcular las coordenadas de un vértice en una partición de Voronoi.
Digamos que tenemos tres sitios A, B y C con coordenadas:
A, equals, left parenthesis, 30, comma, 60, right parenthesis
B, equals, left parenthesis, 90, comma, 80, right parenthesis
C, equals, left parenthesis, 150, comma, 20, right parenthesis
Primero vamos a calcular la ecuación para la mediatriz de start overline, A, B, end overline. Sabemos que esta recta va a pasar por el punto medio de start overline, A, B, end overline y tener el inverso negativo de la pendiente de start overline, A, B, end overline.
Aprende cómo calcular la ecuación de una recta perpendicular aquí.
¿Cuál es el punto medio de start overline, A, B, end overline? left parenthesis
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
,
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
right parenthesis
Aprende sobre puntos medios aquí.

¿Cuál es la pendiente de start overline, A, B, end overline?
  • Tu respuesta debería ser
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4

Aprende cómo calcular el gradiente a partir de dos puntos aquí.

¿Cuál es la pendiente de la mediatriz de start overline, A, B, end overline?
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i

El gradiente de una recta es el inverso negativo del gradiente de la recta a la cual es perpendicular.

¿Cuál es la ecuación de la mediatriz de start overline, A, B, end overline?
y, equals
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
x, plus
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i

La ecuación debe estar en la forma y, equals, m, x, plus, b. Ya calculamos el gradiente, m, y conocemos un par de coordenadas, left parenthesis, x, comma, y, right parenthesis que están sobre la recta. Pon estos números en la ecuación para calcular b.

Ya que tenemos la ecuación para la mediatriz de start overline, A, B, end overline, podemos usar el mismo método para calcular la mediatriz de start overline, B, C, end overline.
¿Cuál es la ecuación de la mediatriz de start overline, B, C, end overline?
y, equals
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
x, plus
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i

Ya que tenemos las ecuaciones de dos mediatrices podemos calcular dónde se intersecan. Si usamos m, start subscript, 1, end subscript y b, start subscript, 1, end subscript para representar la pendiente y la intersección con el eje y de la primera mediatriz, y m, start subscript, 2, end subscript y b, start subscript, 2, end subscript para representar la pendiente y la intersección con el eje y de la segunda mediatriz, tenemos:
y=m1x+b1y=m2x+b2\qquad \begin{aligned} y &= m_1 x + b_1 \\ y &= m_2 x + b_2 \end{aligned}
Entonces:
m1x+b1=m2x+b2m1xm2x=b2b1(m1m2)x=b2b1x=b2b1m1m2\qquad \begin{aligned} m_1 x + b_1 &= m_2 x + b_2 \\ \\ m_1 x - m_2 x &= b_2 - b_1 \\ \\ (m_1 - m_2)x &= b_2 - b_1 \\ \\ x &=\dfrac{b_2 - b_1}{m_1 - m_2} \end{aligned}
Inserta los valores de las pendientes y las intersecciones con el eje y en la ecuación para encontrar la coordenada x del punto de intersección. Después inserta el valor de x en una de las ecuaciones de las mediatrices para encontrar la coordenada y.
¿Dónde se intersecan las mediatrices? left parenthesis
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
,
  • Tu respuesta debería ser
  • un entero, como 6
  • una fracción propia simplificada, como 3, slash, 5
  • una fracción impropia simplificada, como 7, slash, 4
  • un número mixto, como 1, space, 3, slash, 4
  • un decimal exacto, como 0, point, 75
  • un múltiplo de pi, como 12, space, p, i o 2, slash, 3, space, p, i
right parenthesis

Ahora imagínate calcular esto para cientos de sitios. ¡Por eso usamos las computadoras!