Finden der orientierten Bounding Box eines konvexen Rumpfes in XNA mit rotierenden Messschieber

Question

Vielleicht ist dies eher eine mathematische Frage als eine Programmierfrage, aber ich habe versucht, den rotierenden Messschieber-Algorithmus in XNA zu implementieren.

Ich habe eine konvexe Hülle von meinem Punktsatz mit einer monotonen Kette abgeleitet, wie in Wikipedia beschrieben.

Jetzt versuche ich meinen Algorithmus zu modellieren die OBB zu finden, nachdem der hier gefunden: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

Aber ich verstehe nicht, was die DOTPR und CROSSPR Methoden es auf der letzten Seite erwähnt werden sollen zurückgeben.

Ich verstehe, wie man das Punktprodukt von zwei Punkten und das Kreuzprodukt von zwei Punkten erhält, aber es scheint, dass diese Funktionen die Punkt- und Kreuzprodukte von zwei Kanten/Liniensegmenten zurückgeben sollen. Meine Kenntnisse der Mathematik ist zwar begrenzt, aber das ist meine beste Vermutung, was der Algorithmus sucht

public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float crossProduct1 = CrossProduct(segmentA1, segmentB1); 
     return crossProduct1; 
    } 

    public static float CrossProduct(Vector2 v1, Vector2 v2) 
    { 
     return (v1.X * v2.Y - v1.Y * v2.X); 
    } 

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB) 
    { 
     var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA]; 
     var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB]; 

     float dotProduct = Vector2.Dot(segmentA1, segmentB1); 
     return dotProduct; 
    } 

Allerdings, wenn ich diese Methoden verwenden, wie in diesem Teil meines Codes gerichtet ...

  while (PolygonDot(polygon, i, j) > 0) 
      { 
       j = NextIndex(j, polygon); 
      } 

      if (i == 0) 
      { 
       k = j; 
      } 
      while (PolygonCross(polygon, i, k) > 0) 
      { 
       k = NextIndex(k, polygon); 
      } 

      if (i == 0) 
      { 
       m = k; 
      } 
      while (PolygonDot(polygon, i, m) < 0) 
      { 
       m = NextIndex(m, polygon); 
      } 

.it den gleichen Index für j gibt, k, wenn ich ihm einen Test Satz von Punkten geben:

List<Vector2> polygon = new List<Vector2>() 
     { 
      new Vector2(0, 138), 
      new Vector2(1, 138), 
      new Vector2(150, 110), 
      new Vector2(199, 68), 
      new Vector2(204, 63), 
      new Vector2(131, 0), 
      new Vector2(129, 0), 
      new Vector2(115, 14), 
      new Vector2(0, 138), 
     }; 

Beachten sie, dass ich polygon.Reverse diese Punkte im Gegenuhrzeigersinn als ind zu platzieren nennen in dem technischen Dokument von perdue.edu. Mein Algorithmus zum Finden einer konvexen Hülle eines Punktsatzes erzeugt eine Liste von Punkten entgegen dem Uhrzeigersinn, aber unter der Annahme, dass y < 0 höher als y> 0 ist, weil beim Zeichnen auf den Bildschirm 0,0 die obere linke Ecke ist . Das Umkehren der Liste scheint ausreichend zu sein. Ich entferne auch den doppelten Punkt am Ende.

Nach diesem Vorgang werden die Daten:

• Vector2 (115, 14)
• Vector2 (129, 0)
• Vector2 (131, 0)
• Vector2 (204, 63
)
• Vector2 (199, 68)
• Vector2 (150, 110)
• Vector2 (1, 138)
0.123.
• Vector2 (0, 138)

Dieser Test nicht auf der ersten Schleife, wenn i gleich 0 ist und j gleich 3. Es stellt fest, dass das Kreuzprodukt der Linie (115,14) bis (204,63) und die Zeile (204,63) bis (199,68) ist 0. Dann stellt sich heraus, dass das Skalarprodukt der gleichen Zeilen ebenfalls 0 ist, also teilen sich j und k den gleichen Index.

Im Gegensatz dazu, wenn dieser Test-Set gegeben: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C%282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

Mein Code erfolgreich zurückgegeben wird dieses OBB: http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29

ich über den C++ Algorithmus auf http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp gefunden gelesen habe, aber ich bin zu dicht folge ihm vollständig.Es scheint auch sehr anders zu sein als das andere, das in dem obigen Papier beschrieben ist.

Weiß jemand, welchen Schritt ich überspringe oder einen Fehler in meinem Code für das Finden des Punktprodukts und des Kreuzprodukts von zwei Liniensegmenten sehe? Hat jemand diesen Code zuvor in C# implementiert und ein Beispiel?

Answer 1

Ich nehme an, DOTPR ist ein normales Vektor-Dot-Produkt, crosspr ist ein Cross-Produkt. dotproduct gibt eine normale Zahl zurück, crossproduct gibt einen Vektor zurück, der senkrecht zu den beiden angegebenen Vektoren steht. (grundlegende Vektormathematik, check wikipedia)

sie sind tatsächlich in dem Papier als DOTPR (i, j) definiert dotproduct der Vektoren von Vertex i zu i + 1 und j zu j + 1. Gleiches gilt für CROSSPR, aber mit Kreuzprodukt.

Answer 2

Punkte und Vektoren als Datenstrukturen sind im Wesentlichen dasselbe; beide bestehen aus zwei Floats (oder drei, wenn Sie in drei Dimensionen arbeiten). Wenn ich also gefragt werde, das Skalarprodukt der Kanten zu nehmen, nehme ich an, dass es das Skalarprodukt der Vektoren ist, die die Kanten definieren. Der Code, den du zur Verfügung gestellt hast, macht genau das.

Ihre Implementierung von CrossProduct scheint korrekt zu sein (siehe Wolfram MathWorld). Jedoch in PolygonCross und PolygonDot Ich denke, dass Sie die Segmente nicht normalisieren sollten. Es beeinflusst die Größe der Rückgabewerte von PolygonDot und PolygonCross. Durch Entfernen der überflüssigen Aufrufe an Vector2.Normalize können Sie Ihren Code beschleunigen und die Menge an Rauschen in Ihren Fließkommawerten reduzieren. Die Normalisierung ist jedoch für die Richtigkeit des eingefügten Codes nicht relevant, da nur die Ergebnisse mit Null verglichen werden.

Beachten Sie, dass das Papier, auf das Sie verweisen, davon ausgeht, dass die Polygonscheitelpunkte entgegen dem Uhrzeigersinn aufgelistet sind (Seite 5, erster Absatz nach "Beginn der Kommentare"), aber Ihr Beispiel polygon wird im Uhrzeigersinn definiert. Deshalb ist PolygonCross(polygon, 0, 1) negativ und Sie erhalten den gleichen Wert für j und k.