Intersección de rectángulo no alineado con el eje

Question

Estoy tratando de encontrar un algoritmo que calculará la intersección entre 2 rectángulos, que no necesariamente están alineados con el eje, y devolverá la intersección resultante.

This question describe si existe una intersección. Me gustaría tener la forma resultante de la intersección, si existe.

Mi aplicación del algoritmo usará un rectángulo alineado con el eje y uno que no necesariamente esté alineado con el eje, pero sería preferible un algoritmo general.

Gracias!

Answer 1

One algorithm for finding the intersection de dos polígonos convexos consiste en encontrar primero el casco convexo alrededor de todos los vértices. El casco convexo sigue el contorno del polígono que sea más externo; la forma que busca sigue el contorno del polígono que sea más interior, por lo tanto, siga el que el casco convexo no esté siguiendo. Here is a prettier picture del mismo algoritmo.

This extremely brief wiki page menciona otros dos algoritmos. Uno tiene que romper los polígonos en trapecios. La otra es una forma muy inteligente de caminar alrededor de ambos polígonos en sentido antihorario en el paso de bloqueo. Creo que me gusta más esta, pero como dice el wiki, es bastante difícil de describir.

Answer 2

Here's algoritmo de intersección polígono-polígono con fuentes en C y Java, que devuelve el área de intersección.