Estoy escribiendo un programa en Python. Tengo una serie de formas (polígonos, definidas como una secuencia de pares de coordenadas) y necesito saber si se superponen a un rectángulo en particular.Usando Python, ¿cómo puedo saber si un rectángulo y una forma se superponen?
¿Existe un algoritmo sencillo para manejar esto? O mejor, ¿hay una biblioteca de Python pura que pueda manejar estos cálculos por mí?
Suponer que sus "formas arbitrarias" son de hecho polígonos (dado que se describen como pares de coordenadas), determinar si se superponen (en cualquier idioma) es un cálculo relativamente trivial. Simplemente necesita calcular si un lado del polígono A se cruza con cualquier otro lado del polígono B.
Si necesita un ejemplo, hay un tutorial bastante detallado en the Drexel Math Forum.
Hay una serie de módulos de Python que le puede ayudar en esta búsqueda, tales como Sympy, Numpy, PyGame, etc., pero todos ellos son bastante pesado si este es el único cálculo geométrico que necesita para hacer.
Los "lados se cruzan" no funciona, en el caso en que el polígono A contiene completamente el polígono B. –
@Chris Compruebe que el punto de intersección se encuentre entre los puntos finales de ambos lados que está comprobando ('xA1 < = xInt <= xA2 y xB1 <= xInt <= xB2 y yA1 <= yInt <= yA2 y yB1 <= yInt <= yB2') – user470379
@Chris: Si desea incluir la contención, puede usar el interior de las líneas de cruce el polígono Agrega tiempo de cálculo, pero no complejidad. –
¿Son sus formas aribitrary formas realmente aribitrary, o más bien polígonos? ¿La "secuencia de pares de coordenadas" describe los vértices de estos polígonos? Si no, ¿qué es? –
Aclarado en el problema –