Cóncava de la superposición de polígonos de prueba

Question

He puesto de $N$ polígonos cóncavos, dado como lista de 2D Euclidiana coordenadas. Cómo calcular:

una. si cualquiera de ellos se superponen?

b. si uno de los seleccionados arbitrariamente polígono se superpone con cualquiera de los restantes $N-1$ polígonos?

No hay necesidad para la obtención de los puntos de intersección del polígono de las fronteras. La segunda respuesta b es suficiente, pero tal vez también existe especializados algoritmo para responder a una.

Answer 1

Si se cruzan, cada uno de los polígonos deben estar completamente contenida dentro de la otra, o sus bordes deben intersectarse, eso es suficiente para

• elige una al azar vértice de un polígono, y ver si se encuentra dentro de la otra polígono
• compruebe si hay segmentos laterales se cruza.

Si una de estas pruebas devuelve true, entonces se cruzan, de lo contrario no.

Esto puede ser implementado de manera eficiente con un simple barrido de la línea de algoritmo.