Trennung von Achsentest, Erkennung, wenn ein gedrehtes Rechteck ein anderes flaches Rechteck überlappt

Question

Ich habe über Kreuzungspunkte gelesen:

Algorithmus zur Erkennung von Schnittpunkten von zwei Rechtecken?

Aber ich habe Probleme, es zu implementieren.

Wenn R1 (a, b, c, d) mein gedrehtes Rechteck und R2 (a ', b', c ', d') ist, das andere Rechteck ohne Drehung.

Die aus dem obigen Link extrahierte Formel lautet:

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

Sie können ein senkrechtes dazu bringen, indem Sie es um 90 ° drehen. In 2d ist dies einfach:

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

Meine gedrehten Kanten stammen von R1 mit

AB (xb-xa, yb-ya) ist so gedreht x ist xb-xa? BC (XC-XB, YC-Y1) CD ... AD ...

Testpoint wird a ', b', c ', d' von R2 sein, daher muss ich das Zeichen des Ergebniss aus allen Punkten von R2 anhand der 4 Kanten von R1 überprüfen. Das ist 16 Vergleiche, wenn sich überschneidet. Woher weiß ich, ob ich eine Trennkante gefunden habe?

Vielen Dank

Answer 1

Wenn für eine bestimmte Kante die Anzeichen eines der DOT -Produkttests gegen diese Kante nicht übereinstimmen, dann haben Sie eine Kreuzung. Das Zeichen des Punktprodukts ist für alle Punkte auf einer Seite der Linie gleich.