Detectando si el ángulo es más de 180 grados

Question

Estoy trabajando en un problema que el profesor asignó, y estoy teniendo un problema buscando una forma de detectar si el ángulo entre 3 puntos es más de 180 grados, por ejemplo:

I desea detectar si alfa es más de 180 grados. De todos modos, mi profesor tiene un código que resuelve el problema, pero tiene una función llamada zcross, pero no sé exactamente cómo funciona. ¿Alguien podría decirme? Su código está aquí:

#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

Primero, sabemos que si sin(a) es negativo, entonces el ángulo es más de 180 grados.

¿Cómo encontramos el signo de sin(a)? Aquí es donde el producto cruzado entra en juego.

En primer lugar, vamos a definir dos vectores:

v1 = p1-p2 
v2 = p3-p2 

Esto significa que los dos vectores comienzan en p2 y se apunta hacia p1 y los otros puntos a p3.

producto cruz se define como:

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

Desde sus vectores son en 2D, a continuación, z1 y z2 son 0 y por lo tanto:

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

es por eso que lo llaman zcross porque solo el elemento z del producto tiene un valor distinto de 0.

Ahora, por otro lado, w e saber que:

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

donde ||v|| es la norma (tamaño) de vectores v. Además, sabemos que si el ángulo a es menor que 180, entonces v1 x v2 apuntará hacia arriba (regla de la mano derecha), mientras que si es mayor de 180 apuntará hacia abajo. Así que en su caso especial:

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

En pocas palabras, si el valor z de v1 x v2 es positivo, entonces a es menor que 180. Si el resultado es negativo, entonces es más grande (El valor de z era x1y2-x2y1). Si el producto cruzado es 0, entonces los dos vectores son paralelos y el ángulo es 0 o 180, dependiendo de si los dos vectores tienen respectivamente la misma dirección o la dirección opuesta.

Answer 2

zcross está utilizando la señal de la vector cross product (más o menos en la dirección z) para determinar si el ángulo es más o menos de 180 grados, como lo ha incluido.

Answer 3

Otra manera de hacerlo sería la siguiente:

calcular vectores v1 = p2-p1, p2 = v2 -P3. Luego, use la fórmula de productos cruzados: u.v = || u || || v || cos (theta)

Answer 4

En 3D, encontrar el producto vectorial de los vectores, encontrar la longitud mínima para el producto vectorial que es básicamente sólo encontrar el número más pequeño de x, y, z.

Si el valor más pequeño es menor que 0, el ángulo de los vectores es negativo.

Así que en código:

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