¿Cómo puedo determinar si dos polígonos convexos se cruzan?

Question

Supongamos que hay un número de polígonos convexos en un plano, quizás un mapa. Estos polígonos pueden chocar entre sí y compartir una ventaja, pero no se pueden superponer.

Para probar si dos polígonos P y Q de solapamiento, primero I pueden probar cada borde en P para ver si se cruza con cualquiera de los bordes en Q. Si se encuentra una intersección, declaro que se cruzan P y Q. Si ninguno se cruza, entonces tengo que probar para el caso que P está completamente contenida en Q, y viceversa. A continuación, está el caso de que P == Q. Finalmente, está el caso de compartir algunos bordes, pero no todos. (Estos dos últimos casos probablemente se puedan considerar como el mismo caso general, pero eso podría no ser importante.)

Tengo un algoritmo que detecta dónde se cruzan dos segmentos de línea. Si los dos segmentos son colineales, no se considera que se crucen para mis propósitos.

¿He enumerado correctamente los casos? ¿Alguna sugerencia para probar estos casos?

Tenga en cuenta que no estoy buscando el nuevo polígono convexo que es la intersección, solo quiero saber si existe una intersección. Hay muchos algoritmos bien documentados para encontrar la intersección, pero no necesito hacer todo el esfuerzo.

Answer 1

Usted podría utilizar this collision algorithm:

Para poder decidir si dos polígonos convexos se intersectan (en contacto entre sí) podemos usar el teorema de separación de ejes. Básicamente:

• Si dos polígonos convexos no se intersectan, existe una línea que pasa entre ellos.
• Dicha línea solo existe si uno de los lados de uno de los polígonos forma dicha línea.

La primera afirmación es fácil. Como los polígonos son convexos, podrás dibujar una línea con un polígono en un lado y el otro en el otro lado a menos que se crucen. El segundo es un poco menos intuitivo. Mire la figura 1. A menos que la cara más cercana de los polígonos sea paralela entre sí, el punto donde se acercan más es el punto donde una esquina de un polígono se acerca más a un lado del otro polígono. Este lado formará un eje de separación entre los polígonos. Si los lados son paralelos, ambos son ejes de separación.

Entonces, ¿cómo esta concretamente ayudar a decidir si polígono A y B se cruzan? Bueno, simplemente revisamos cada lado de cada polígono y verificamos si forma un eje de separación. Para hacer esto, utilizaremos algunas matemáticas vectoriales básicas para aplastar todos los puntos de ambos polígonos en una línea perpendicular a la línea de separación potencial (ver figura 2). Ahora todo el problema es convenientemente de 1 dimensión. Podemos determinar una región en la que se encuentran los puntos para cada polígono, y esta línea es un eje separador si estas regiones no se superponen.

Si, después de revisar cada línea de ambos polígonos, se ha encontrado ningún eje que separa, se ha demostrado que los polígonos se cruzan y algo tiene que hacerse al respecto.

Answer 2

Sus casos de prueba deberían funcionar, ya que está comprobando el caso donde los polígonos no se cruzan (completamente afuera o completamente adentro), así como donde hay alguna forma de intersección parcial (los bordes se intersecan siempre si hay superposición).

Para las pruebas, simplemente me aseguraría de probar todas las combinaciones posibles. El que falta por encima de lo que veo es un borde único compartido, pero un poli contiene en el otro. También agregaría pruebas para algunas formas de poli más complejas, desde tri -> muchas caras, solo como precaución.

Además, si tuviera un poliuretano en forma de U que rodeara por completo el poliuretano, pero no se superpusiera, creo que su caso manejaría eso, pero también lo agregaría como un control.

Answer 3

• si los polígonos son siempre convexa, primero calcular el ángulo de una línea trazada desde el centro a centro de los polígonos. a continuación, puede eliminar la necesidad de probar segmentos de borde en la mitad del polígono (s) a 180 grados de distancia del otro polígono (s).

• para eliminar los bordes, comience con el polígono de la izquierda. tome el segmento de línea desde el centro del polígono que es perpendicular al segmento de línea desde la viñeta anterior, y toca ambos lados del polígono. llame a este segmento de línea p, con los vértices p1 y p2. Luego, para todos los vértices si la coordenada x es menor que p1.x y p2.x, ese vértice puede ir en el "cubo seguro".

• si no lo hace, usted tiene que comprobar para asegurarse de que está en el lado "seguro" de la línea (sólo comprobar las coordenadas Y demasiado)

-si un segmento de línea en el polígono tiene todos los vértices en el "cubo seguro", puedes ignorarlo.

-reverse la polaridad para que esté "orientado correctamente" para el segundo polígono.

Answer 4

Dado que altCognito ya le dio una solución, solo señalaré an excellent book on computational geometry que le pueden interesar.

Answer 5

He aquí una idea:

• encontrar el punto central de cada polígono

• Encuentra los dos puntos de cada polígono más cercano al punto central de la otra. Serán puntos adyacentes en polígonos convexos. Estos definen el borde más cercano de cada polígono, llamemos a los puntos {A, B} y {Y, Z}

• Encuentra la intersección de las líneas AB e YZ.Si los segmentos de línea se cruzan (la intersección en AB se encuentra entre A y B), sus polígonos se cruzan. Si AB y XY son paralelos, ignore esta condición, el siguiente paso atrapará el problema.

• Hay un caso más que debe verificar, que es cuando los polígonos se cruzan lo suficiente como para que AB y XY se crucen completamente y no se crucen. Para atrapar este caso, calcule las distancias perpendiculares de AB y XY a los puntos centrales de cada polígono. Si alguno de los puntos centrales está más cerca del segmento de línea del polígono opuesto, su polígono se superpone fuertemente.

Answer 6

GJKcollisiondetectionshouldwork.

Answer 7

Existen varias formas de detectar intersección y/o contención entre polígonos convexos. Todo depende de qué tan eficiente quieras que sea el algoritmo. Considere dos polígonos convexos R y B con vértices r y b, respectivamente:

1. Sweep line algoritmo basado. Como mencionó, puede realizar un procedimiento de línea de barrido y mantener los intervalos resultantes de la intersección de los polígonos con la línea de barrido. Si en algún momento los intervalos se superponen, entonces los polígonos se cruzan. La complejidad es el tiempo O ((r + b) log (r + b)).
2. Rotating Callipers algoritmo basado. Vea here y here para más detalles. La complejidad es O (r + b) tiempo.
3. Los métodos más eficientes se pueden encontrar here y here. Estos algoritmos toman el tiempo O (log r + log b).