Encontrar la caja delimitadora orientada de un casco convexo en XNA con pinzas giratorias

Question

Quizás esta sea más una cuestión matemática que una cuestión de programación, pero he estado tratando de implementar el algoritmo rotativo de calibradores en XNA.

He deducido un casco convexo de mi conjunto de puntos utilizando una cadena monótona como se detalla en wikipedia.

Ahora estoy tratando de modelar mi algoritmo para encontrar el OBB después de la que se encuentra aquí: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

Sin embargo, no entiendo lo que se supone que los métodos DOTPR y CROSSPR se menciona en la página final regresar.

Entiendo cómo obtener el producto Punto de dos puntos y el Producto Cruzado de dos puntos, pero parece que se supone que estas funciones devuelven los puntos y productos cruzados de dos segmentos de bordes/líneas. Mi conocimiento de las matemáticas está ciertamente limitado, pero este es mi mejor conjetura en cuanto a lo que el algoritmo está buscando

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

Sin embargo, cuando se utiliza esos métodos como se indica en esta parte de mi código ...

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

..es devuelve el mismo índice para j, k cuando le dan una prueba de conjunto de puntos:

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

Nota, que llamo polygon.Reverse para colocar estos puntos en sentido contrario a las agujas del reloj como se ind en el documento técnico de perdue.edu. Mi algoritmo para encontrar un casco convexo de un conjunto de puntos genera una lista de puntos en el sentido contrario a las agujas del reloj, pero lo hace suponiendo que y < 0 es mayor que y> 0 porque cuando se dibuja en la pantalla 0,0 es la esquina superior izquierda . Invertir la lista parece suficiente. También elimino el punto duplicado al final.

Después de este proceso, los datos se convierte en:

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

esta prueba falla en el primer bucle cuando i es igual a 0 y j es igual a 3. Se encuentra que el producto cruzado de la línea (115,14) a (204,63) y la línea (204,63) a (199,68) es 0. Luego encuentra que el producto de puntos de las mismas líneas también es 0, por lo que j y k comparten el mismo índice.

Por el contrario, cuando se administra este conjunto de pruebas: 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

Mi código devuelve con éxito este 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

que he leído sobre el algoritmo de C++ que se encuentra en http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp pero estoy demasiado denso para sígalo completamente.También parece ser muy diferente al otro detallado en el documento anterior.

¿Alguien sabe qué paso me estoy salteando o veo algún error en mi código para encontrar el producto escalar y el producto cruzado de dos segmentos de línea? ¿Alguien ha implementado con éxito este código antes en C# y tiene un ejemplo?

Answer 1

Supongo que DOTPR es un producto vectorial punto normal, crosspr es un producto cruzado. dotproduct devolverá un número normal, crossproduct devolverá un vector que es perpendicular a los dos vectores dados. (matemáticas básica de vectores, consultar wikipedia)

En realidad, se definen en el documento como DOTPR (i, j) devuelve el producto de puntos de los vectores del vértice i a i + 1 y j a j + 1. lo mismo para CROSSPR pero con producto cruzado.

Answer 2

Los puntos y vectores como estructuras de datos son esencialmente lo mismo; ambos consisten en dos carrozas (o tres si trabajas en tres dimensiones). Entonces, cuando me piden que tome el producto escalar de los bordes, supongo que significa tomar el producto escalar de los vectores que definen los bordes. El código que proporcionó hace exactamente esto.

Su implementación de CrossProduct parece correcta (consulte Wolfram MathWorld). Sin embargo, en PolygonCross y PolygonDot, creo que no debe normalizar los segmentos. Afectará la magnitud de los valores de retorno de PolygonDot y PolygonCross. Al eliminar las llamadas superfluas al Vector2.Normalize puede acelerar su código y reducir la cantidad de ruido en sus valores de coma flotante. Sin embargo, la normalización no es relevante para la corrección del código que ha pegado, ya que solo compara los resultados con cero.

Observe que el papel al que hace referencia supone que los vértices del polígono se enumeran en sentido antihorario (página 5, primer párrafo después del "Comienzo de comentarios") pero su ejemplo polygon se define en sentido horario. Es por eso que PolygonCross(polygon, 0, 1) es negativo y obtienes el mismo valor para j y k.