algorithm - computational - Intersección rectangular no alineada con el eje

cgal

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.

Esta pregunta 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

Aquí hay un algoritmo de intersección polígono-polígono con fuentes en C y Java, que devuelve el área de intersección.

Answer 2

Un algoritmo para encontrar la intersección de dos polígonos convexos implica primero encontrar el casco convexo alrededor de todos los vértices. El casco convexo sigue el contorno del polígono más externo ; la forma que busca sigue el contorno del polígono que esté más adentro , por lo tanto, siga el que el casco convexo no esté siguiendo. Aquí hay una imagen más bonita del mismo algoritmo.

Esta página wiki extremadamente breve 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 este, pero como dice el wiki, es bastante difícil de describir.