Test dell'asse di separazione, rilevando se un rettangolo ruotato si sovrappone a un altro rettangolo piatto

Question

Ho letto dei rettangoli di intersezione su:

Algoritmo per rilevare l'intersezione di due rettangoli?

Ma ho difficoltà a implementarlo.

Se R1 (A, B, C, D) è il mio rettangolo ruotato e R2 (A ', B', C ', D') l'altro rettangolo senza rotazione.

La formula estratta dal link sopra è:

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

Puoi ottenere una perpendicolare ruotandola di 90 & # 176 ;. In 2D questo è facile come:

  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);

I miei bordi ruotati verranno da R1 con

AB (xB-xA, yB-yA) così ruotato x è xB-xA? BC (xC-xB, yC-y1) CD ... AD ...

Testpoint sarà A ', B', C ', D' da R2 Quindi devo controllare il segno del risultato da tutti i punti di R2 contro i 4 bordi di R1. Ecco 16 confronti se si intersecano. Come faccio a sapere se ho trovato un bordo di separazione?

Grazie

Answer 1

Se per un dato bordo, i segni di uno qualsiasi dei prodotti punto test su quel bordo non corrispondono, allora hai un'intersezione. Il segno del prodotto punto sarà lo stesso per tutti i punti su un lato della linea.