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

Question

Supongamos que hay una serie de polígonos convexos en un avión, tal vez un mapa. Estos polígonos pueden chocar uno contra el otro y comparten un borde, pero no se pueden superponer.

Para probar si dos polígonos P y Q solapamiento, primero I puede 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 P y Q se cruzan. Si ninguno se cruzan, entonces me tengo que probar para el caso de que P está completamente dentro de Q , y viceversa. A continuación, está el caso de que P == Q . Por último, está el caso de que comparten un par de bordes, pero no todos ellos. (Estos dos últimos casos, probablemente, pueden ser considerados como el mismo caso general, pero que podría no ser importante.)

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

¿He enumerado adecuadamente los casos? ¿Alguna sugerencia para las pruebas para estos casos?

Tenga en cuenta que no estoy en busca de encontrar el nuevo polígono convexo que es la intersección, sólo quiero saber si existe una intersección. Hay muchos algoritmos bien documentados para encontrar la intersección, pero no tienen que pasar por todo el esfuerzo.

Answer 1

Se puede usar este algoritmo de colisión :

  

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

     

  
• Si dos polígonos convexos no se intersectan, no existe una línea que pasa entre ellos.
  
• Tal línea sólo existe si uno de los lados de uno de los polígonos forma una línea tales.
  

     

La primera afirmación es fácil. Dado que los polígonos son ambos convexa, podrás dibujar una línea con un polígono de un lado y del otro polígono en el otro lado a menos que se intersectan. El segundo es ligeramente menos intuitivo. Vistazo a la figura 1. A menos que el más cercano caras de los polígonos son paralelas entre sí, el punto donde consiguen más cerca el uno al otro es el punto en una esquina de un polígono más se aproxima a un lado del otro polígono. Este lado formará entonces un eje de separación entre los polígonos. Si los lados son paralelos, ambos son la separación de ejes.

     

     

Entonces, ¿cómo esta concretamente ayudar a decidir si polígono A y B se cruzan? Bueno, acabamos de repasar cada lado de cada polígono y comprobamos si se forma un eje de separación. Para ello vamos a utilizar un poco de matemática básica del vector para aplastar a todos los puntos de ambos polígonos en una línea que es perpendicular a la línea de separación de potencial (ver figura 2). Ahora el problema es convenientemente de 1 dimensión. Podemos determinar una región en la que los puntos para cada polígono mentira, y esta línea es un eje de separación 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

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

• para eliminar los bordes, comience con el polígono de la izquierda. tomar el segmento de línea desde el centro del polígono que es perpendicular al segmento de línea desde el punto anterior, y toca ambos lados del polígono. llamar a este segmento de línea p, con vértices P1 y P2. Entonces, 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 de seguro".

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

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

rebobinen la polaridad, por lo que está "bien orientado" para el segundo polígono.

Answer 3

Sus casos de prueba deben trabajar, ya que se esté examinando el caso en que los polígonos no se cruzan en absoluto (completamente fuera o completamente en el interior), así como donde hay alguna forma de intersección parcial (bordes se cruzan siempre si hay es la superposición).

Para las pruebas, yo sólo asegúrese de probar todas las combinaciones posibles. La que se perdió por encima de lo que veo es una ventaja única compartida, pero una poli contenida en la otra. También me gustaría añadir pruebas para algunas formas poli más complejas, de tri -.> Muchas caras, simplemente por precaución

Además, si usted tenía un poli en forma de U que rodeaba por completo la poli, pero no se superponen, creo que su caso podría manejar eso, pero me gustaría añadir que como un cheque, también.

Answer 4

Desde altCognito ya le dio una solución, voy a señalar solamente un excelente libro sobre la geometría computacional que pueden interesarle.

Answer 5

GJK colisión detección debe el trabajo .

Answer 6

He aquí una idea:

• Encuentra el punto central de cada polígono

• Para 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, vamos a llamar a los puntos {A, B} y {Y, Z}

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

• Hay un caso más que necesita para comprobar si hay, que es cuando los polígonos se cruzan en gran medida suficiente como para que AB y XY son completamente más allá de nosotros y en realidad no se cruzan. Para atrapar este caso, el cálculo de las distancias perpendiculares de AB y XY para cada uno de los puntos centrales polígonos. Si bien el punto central está más cerca de la línea segmento del polígono opuesta a su polígono de solapamiento en gran medida.

Answer 7

Hay varias maneras de detectar intersección y / o contención entre polígonos convexos. Todo depende de qué tan eficiente desea que el algoritmo sea. Consideremos dos polígonos convexos R y B con R y B vértices, respectivamente:

1. línea de barrido algoritmo basado. Como usted ha mencionado se 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 cualquier momento los intervalos se superponen, a continuación, los polígonos se cruzan. La complejidad es O ((r + b) log (r + b)) tiempo.
2. giratorios Calibradores algoritmo basado. Ver aquí y aquí para más detalles. La complejidad es O (r + b) tiempo.
3. Los métodos más eficientes se pueden encontrar aquí y aquí . Estos algoritmos toman O (log r + log b) tiempo.