Rilevare se l'angolo è superiore a 180 gradi

Question

Sto lavorando su un problema assegnato dal professore e sto riscontrando un problema alla ricerca di un modo per rilevare se l'angolo tra 3 punti è superiore a 180 gradi, ad esempio:

voglio rilevare se alfa è più di 180 gradi. Ad ogni modo, il mio professore ha un codice che risolve il problema, ma ha una funzione chiamata zcross, ma non so esattamente come funzioni. Qualcuno potrebbe dirmelo? Il suo codice è qui:

#include <fstream.h> 
#include <math.h> 
#include <stdlib.h> 

struct point { 
    double x; 
    double y; 
    double angle; 
}; 

struct vector { 
    double i; 
    double j; 
}; 

point P[10000]; 
int  hull[10000]; 

int 
zcross (vector * u, vector * v) 
{ 
    double p = u->i * v->j - v->i * u->j; 
    if (p > 0) 
    return 1; 
    if (p < 0) 
    return -1; 
    return 0; 
} 

int 
cmpP (const void *a, const void *b) 
{ 
    if (((point *) a)->angle < ((point *) b)->angle) 
    return -1; 
    if (((point *) a)->angle > ((point *) b)->angle) 
    return 1; 
    return 0; 
} 

void 
main() 
{ 
    int  N, i, hullstart, hullend, a, b; 
    double midx, midy, length; 
    vector v1, v2; 

    ifstream fin ("fc.in"); 
    fin >> N; 
    midx = 0, midy = 0; 
    for (i = 0; i < N; i++) { 
     fin >> P[i].x >> P[i].y; 
     midx += P[i].x; 
     midy += P[i].y; 
    } 
    fin.close(); 
    midx = (double) midx/N; 
    midy = (double) midy/N; 
    for (i = 0; i < N; i++) 
     P[i].angle = atan2 (P[i].y - midy, P[i].x - midx); 
    qsort (P, N, sizeof (P[0]), cmpP); 

    hull[0] = 0; 
    hull[1] = 1; 
    hullend = 2; 
    for (i = 2; i < N - 1; i++) { 
     while (hullend > 1) { 
      v1.i = P[hull[hullend - 2]].x - P[hull[hullend - 1]].x; 
      v1.j = P[hull[hullend - 2]].y - P[hull[hullend - 1]].y; 
      v2.i = P[i].x - P[hull[hullend - 1]].x; 
      v2.j = P[i].y - P[hull[hullend - 1]].y; 
      if (zcross (&v1, &v2) < 0) 
       break; 
      hullend--; 
     } 
     hull[hullend] = i; 
     hullend++; 
    } 

    while (hullend > 1) { 
     v1.i = P[hull[hullend - 2]].x - P[hull[hullend - 1]].x; 
     v1.j = P[hull[hullend - 2]].y - P[hull[hullend - 1]].y; 
     v2.i = P[i].x - P[hull[hullend - 1]].x; 
     v2.j = P[i].y - P[hull[hullend - 1]].y; 
     if (zcross (&v1, &v2) < 0) 
      break; 
     hullend--; 
    } 
    hull[hullend] = i; 

    hullstart = 0; 
    while (true) { 
     v1.i = P[hull[hullend - 1]].x - P[hull[hullend]].x; 
     v1.j = P[hull[hullend - 1]].y - P[hull[hullend]].y; 
     v2.i = P[hull[hullstart]].x - P[hull[hullend]].x; 
     v2.j = P[hull[hullstart]].y - P[hull[hullend]].y; 
     if (hullend - hullstart > 1 && zcross (&v1, &v2) >= 0) { 
      hullend--; 
      continue; 
     } 
     v1.i = P[hull[hullend]].x - P[hull[hullstart]].x; 
     v1.j = P[hull[hullend]].y - P[hull[hullstart]].y; 
     v2.i = P[hull[hullstart + 1]].x - P[hull[hullstart]].x; 
     v2.j = P[hull[hullstart + 1]].y - P[hull[hullstart]].y; 
     if (hullend - hullstart > 1 && zcross (&v1, &v2) >= 0) { 
      hullstart++; 
      continue; 
     } 
     break; 
    } 

    length = 0; 
    for (i = hullstart; i <= hullend; i++) { 
     a = hull[i]; 
     if (i == hullend) 
      b = hull[hullstart]; 
     else 
      b = hull[i + 1]; 
     length += sqrt ((P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y)); 
    } 

    ofstream fout ("fc.out"); 
    fout.setf (ios: :fixed); 
    fout.precision (2); 
    fout << length << '\n'; 
    fout.close(); 
} 

Answer 1

Innanzitutto, sappiamo che se sin(a) è negativo, l'angolo è più di 180 gradi.

Come troviamo il segno di sin(a)? Qui è dove entra in gioco il prodotto trasversale.

In primo luogo, definiamo due vettori:

v1 = p1-p2 
v2 = p3-p2 

Ciò significa che i due vettori partono p2 e una punta a p1 e gli altri punti di p3.

prodotto trasversale è definita come:

(x1, y1, z1) x (x2, y2, z2) = (y1z2-y2z1, z1x2-z2x1, x1y2-x2y1) 

Dal momento che i vettori in 2D, quindi z1 e z2 sono 0 e quindi:

(x1, y1, 0) x (x2, y2, 0) = (0, 0, x1y2-x2y1) 

Ecco perché lo chiamano zcross perché solo l'elemento z del prodotto ha un valore diverso da 0.

Ora, d'altra parte, w e sapere che:

||v1 x v2|| = ||v1|| * ||v2|| * abs(sin(a)) 

dove ||v|| è la norma (dimensione) del vettore v. Inoltre, sappiamo che se l'angolo a è inferiore a 180, allora v1 x v2 punterà verso l'alto (regola della mano destra), mentre se è maggiore di 180 punterà verso il basso. Quindi nel tuo caso particolare:

(v1 x v2).z = ||v1|| * ||v2|| * sin(a) 

poche parole, se il valore z di v1 x v2 è positiva, allora a è minore di 180. Se è negativo, allora è più grande (il valore Z era x1y2-x2y1). Se il prodotto incrociato è 0, i due vettori sono paralleli e l'angolo è 0 o 180, a seconda che i due vettori abbiano rispettivamente la direzione identica o opposta.

Answer 2

zcross sta usando il segno della vector cross product (più o meno nella direzione z) per determinare se l'angolo è più o meno di 180 gradi, come hai messo.

Answer 3

Un altro modo per farlo sarebbe come segue:

Calcolare vettore v1 = p2-p1, p2 = v2 -P3. Quindi, utilizzare la formula del cross-product: u.v = || u || || v || cos (theta)

Answer 4

In 3D, trovare il prodotto incrociato dei vettori, trovare la lunghezza minima per il prodotto incrociato che in pratica è solo trovare il numero più piccolo di x, yez.

Se il valore più piccolo è minore di 0, l'angolo dei vettori è negativo.

Così in codice:

float Vector3::Angle(const Vector3 &v) const 
{ 
    float a = SquareLength(); 
    float b = v.SquareLength(); 
    if (a > 0.0f && b > 0.0f) 
    { 
     float sign = (CrossProduct(v)).MinLength(); 
     if (sign < 0.0f) 
      return -acos(DotProduct(v)/sqrtf(a * b)); 
     else 
      return acos(DotProduct(v)/sqrtf(a * b)); 
    } 
    return 0.0f; 
}