Trovare la scatola di contenimento orientata di uno scafo convesso in XNA usando le pinze rotanti

Question

Forse questa è più una questione di matematica che una domanda di programmazione, ma ho cercato di implementare l'algoritmo dei calibri rotanti in XNA.

Ho dedotto uno scafo convesso dal mio set di punti utilizzando una catena monotona come dettagliato su wikipedia.

Ora sto cercando di modellare il mio algoritmo per trovare l'OBB dopo quello che si trova qui: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

Tuttavia, non capisco quello che i metodi DOTPR e CROSSPR si menziona nella pagina finale si suppone ritornare.

Capisco come ottenere il Prodotto punto di due punti e il Prodotto incrociato di due punti, ma sembra che queste funzioni debbano restituire il punto e i prodotti incrociati di due segmenti/segmenti di linea. La mia conoscenza della matematica è certamente limitato, ma questo è il mio migliore ipotesi su ciò che l'algoritmo è alla ricerca di

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

Tuttavia, quando uso questi metodi come indicato in questa porzione del mio codice ...

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

..è restituisce lo stesso indice per j, k, quando gli ho dato una serie di test di punti:

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, che io chiamo polygon.Reverse per posizionare questi punti in modo antiorario come ind icated nel documento tecnico da perdue.edu. Il mio algoritmo per trovare uno scafo convesso di un set di punti genera un elenco di punti in senso antiorario, ma supponendo che y < 0 sia maggiore di y> 0 perché quando si disegna sullo schermo 0,0 è l'angolo in alto a sinistra . Invertire l'elenco sembra sufficiente. Rimuovo anche il punto duplicato alla fine.

Dopo questo processo, i dati diventano:

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

Questo test fallisce al primo ciclo quando ièuguale 0 e j è uguale a 3. Si ritiene che il prodotto incrociato della linea (115,14) a (204,63) e la riga (204,63) a (199,68) è 0. Quindi trova che il prodotto punto delle stesse linee è anche 0, quindi j e k condividono lo stesso indice.

Al contrario, quando somministrato il test set: 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

mio codice restituisce con successo questo 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

ho letto sopra l'algoritmo C++ trovato su http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp ma sono troppo densi per seguilo completamente.Sembra anche essere molto diverso da quello dettagliato nel documento di cui sopra.

Qualcuno sa quale passaggio sto saltando o vedo qualche errore nel mio codice per trovare il prodotto punto e il prodotto incrociato di due segmenti di linea? Qualcuno ha implementato con successo questo codice prima in C# e ha un esempio?

Answer 1

Suppongo che DOTPR sia un normale prodotto con punto vettoriale, crosspr è un prodotto incrociato. dotproduct restituirà un numero normale, crossproduct restituirà un vettore che è perpendicolare ai due vettori dati. (matematica vettoriale di base, controllo wikipedia)

sono effettivamente definiti nella carta come DOTPR (i, j) restituisce dotproduct di vettori dal vertice i a i + 1 e j a j + 1. lo stesso per CROSSPR ma con prodotto incrociato.

Answer 2

Punti e vettori come strutture di dati sono essenzialmente la stessa cosa; entrambi consistono in due galleggianti (o tre se lavori in tre dimensioni). Quindi, quando viene chiesto di prendere il prodotto punto dei bordi, suppongo significhi prendere il prodotto punto dei vettori che definiscono i bordi. Il codice che hai fornito fa esattamente questo.

L'implementazione di CrossProduct sembra corretta (vedere Wolfram MathWorld). Tuttavia, in PolygonCross e PolygonDot penso che non dovresti normalizzare i segmenti. Influirà sulla grandezza dei valori di ritorno di PolygonDot e PolygonCross. Rimuovendo le chiamate superflue a Vector2.Normalize è possibile velocizzare il codice e ridurre la quantità di rumore nei valori in virgola mobile. Tuttavia, la normalizzazione non è rilevante per la correttezza del codice che hai incollato poiché confronta solo i risultati con zero.

Si noti che la carta a cui si fa riferimento presuppone che i vertici del poligono siano elencati in ordine in senso antiorario (pagina 5, primo paragrafo dopo "Inizio dei commenti") ma l'esempio polygon è definito in senso orario. Ecco perché PolygonCross(polygon, 0, 1) è negativo e ottieni lo stesso valore per j e k.