Prueba de eje de separación, que detecta si un rectángulo girado se superpone a otro rectángulo plano

Question

Leí sobre rectángulos de intersección en:

¿Algoritmo para detectar la intersección de dos rectángulos?

Pero tengo problemas para implementarlo.

Si R1 (A, B, C, D) es mi rectángulo girado y R2 (A ', B', C ', D') el otro rectángulo sin rotación.

La fórmula extraída del enlace anterior es:

  edge = v(n) - v(n-1)

Puede obtener una perpendicular a esto girándola 90 & # 176 ;. En 2D esto es fácil como:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Mis bordes girados serán de R1 con

AB (xB-xA, yB-yA) de modo que x sea xB-xA? BC (xC-xB, yC-y1) DISCOS COMPACTOS ... AD ...

El punto de prueba será A ', B', C ', D' de R2 Así que tengo que verificar el signo del resultado de todos los puntos de R2 contra los 4 bordes de R1. Eso es 16 comparaciones si se cruzan. ¿Cómo puedo saber si he encontrado un borde de separación?

Gracias

Answer 1

Si para cualquier borde dado, los signos de cualquiera de los productos de punto que prueban contra ese borde no coinciden, entonces hay una intersección. El signo del producto de puntos será el mismo para todos los puntos en un lado de la línea.