Cómo saber si dos polígonos dados se cruzan / se superponen Educación te da un futuro mejor

Al responder a esta pregunta de JavaScript Point Collision with Regular Hexagon en Stackoverflow, en mi mente, formé un algoritmo que estoy bastante seguro de que es muy eficiente para aplicaciones tan complicadas.

Es simplemente una cuestión de representar el polígono como una sola función. Una función de [math] \ theta [/ math] en este caso.

Ingrese la transformación discreta de Fourier .

No sé si esto se ha implementado antes (conozco los descriptores de Fourier) pero es bastante sencillo no solo para un polígono convexo o cóncavo regular. Todavía no lo he puesto en código ya que tengo algunas otras cosas como prioridad en mi mente en este momento. Alguien conoce un enfoque similar, por favor hágamelo saber.

OK … ¿Qué representa el polígono como una función única de [math] \ theta [/ math]? Una idea podría ser dibujar los polígonos en el plano complejo de modo que cada vértice del polígono esté representado por un número complejo como 3 + 4i en lugar de las coordenadas x e y (3,4).

Por ejemplo, en la siguiente figura, el polígono rojo tiene 6 vértices básicos como [matemática] 3 + 4i [/ matemática], [matemática] -2 + 3i [/ matemática], [matemática] -1 + i [/ matemática], [ matemática] -3-i [/ matemática], [matemática] 2–2i [/ matemática], [matemática] 1 + i [/ matemática] mientras que la verde tiene 4 vértices principales como [matemática] 2 + 3i [/ matemática ], [matemáticas] -2 + 2i [/ matemáticas], [matemáticas] -4-i [/ matemáticas], [matemáticas] -2-3i [/ matemáticas].

Lo que haremos es representar estos polígonos como datos de series de tiempo mediante la recopilación de los vértices de forma ordenada en sentido antihorario y aplicar FFT (Transformada rápida de Fourier) para cada polígono. Para FFT necesitamos datos [matemáticos] 2 ^ n [/ matemáticos] (vértices aquí). Entonces, por simplicidad, usemos solo 16 vértices por polígono. (Si usamos más como 32 o incluso 64, se separarán de manera más uniforme y se obtendrá una representación más precisa de nuestro polígono en el dominio de la frecuencia). Así que solo calcule vértices adicionales usando trigonometría simple. Nuestra figura es ahora la siguiente;

Entonces, como puede ver, tenemos 16 vértices para el rojo a partir de [matemática] 1.33 + 0i [/ matemática] en sentido antihorario y 16 vértices para el verde a partir de [matemática] 0 + 0i [/ matemática] en sentido antihorario.

Entonces, FFT nos dará [matemática] n [/ matemática] muchos (0–15) coeficientes complejos que se multiplicarán por los [matemáticos] \ cos (n \ theta) + i \ sin (n \ theta) [/ matemáticos] correspondientes función. La suma de estas 16 funciones nos dará la función del polígono en la variable [math] \ theta [/ math]. Una cosa a tener en cuenta es que, dado que tenemos datos complejos, los 16 coeficientes resultantes deben interpretarse de la siguiente manera; (Primero, el componente DC como [math] 0 \ theta [/ math]) y luego [math] \ theta [/ math], [math] 2 \ theta [/ math], [math] 3 \ theta [ / matemática], [matemática] 4 \ theta [/ matemática], [matemática] 5 \ theta [/ matemática], [matemática] 6 \ theta [/ matemática], [matemática] 7 \ theta [/ matemática], [matemática ] 8 \ theta [/ math] (Nyquist), [math] -7 \ theta [/ math], [math] -6 \ theta [/ math], [math] -5 \ theta [/ math], [math ] -4 \ theta [/ math], [math] -3 \ theta [/ math], [math] -2 \ theta [/ math], [math] – \ theta [/ math].

Entonces, solo para dar una idea, he transferido el polígono rojo al dominio de frecuencia y ahora es una sola función de fase. Por supuesto, ya que solo hemos tomado 16 muestras y aunque todos los vértices están perfectamente cubiertos, todavía es una pequeña papa. 32 muestras producirían una aproximación mucho mejor. Sin embargo, incluso con esta forma, puede hacer una buena detección de colisión.

Entonces, una vez que representamos cada polígono como una función de [math] \ theta [/ math], todo lo que necesitamos es escanear a lo largo de sus bordes en sus lados más cercanos. También en este punto me gustaría mencionar que el componente DC de la representación de Fourier de cada polígono es, de hecho, las coordenadas de sus centroides. Esta es una información gratuita (como en cerveza gratis) pero valiosa para que nuestro algoritmo funcione. Ok vamos a dibujar y mostrar el polígono verde en “papa” también junto con sus centroides.

Ahora podemos calcular que el ángulo entre los dos centroides es [matemática] 0.422 [/ matemática] radianes y, en consecuencia, podemos escanear el polígono rojo comenzando desde [matemática] \ pi + 0.422–0.5 [/ matemática] a [matemática] \ pi + 0.422 + 0.5 [/ matemáticas] radianes y el verde a partir de [matemáticas] 0.422 + 0.5 [/ matemáticas] a [matemáticas] 0.422–0.5 [/ matemáticas] radianes y verifique si los puntos correspondientes en los polígonos rojo y verde son en el orden de los centroides (como el verde a la izquierda y el rojo a la derecha) Un único punto de contradicción revelará una colisión. En este caso particular, todos los puntos en el rango de exploración son contradictorios.

La belleza de este enfoque es

Una vez que transforma sus polígonos en dominio de frecuencia, no necesita repetir esta cosa FFT nunca. Moverlos significa solo alterar el componente DC. Todo lo que necesita es hacer controles en un rango estrecho cada vez que uno de ellos o ambos se muevan.
Se puede aplicar fácilmente a formas muy complejas.
La eficiencia de este algoritmo se puede aumentar al reducir el rango de escaneo. Esto reducirá drásticamente el número de operaciones. También puede reducir la resolución de los ángulos de escaneo como puede hacer solo uno por [math] \ frac {\ pi} {45} [/ math] en lugar de [math] \ frac {\ pi} {180} [/ math ], o incluso para menos escaneos alrededor del lado relacionado del polígono. Tan genial ..! Gracias señor Fourier.