tutorial - Detectar si el ángulo es más de 180 grados.

programming algorithms

Question

Estoy trabajando en un problema que el profesor asignó, y tengo un problema para encontrar una manera de detectar si el ángulo entre 3 puntos es más de 180 grados, por ejemplo:

Quiero detectar si el alfa tiene 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

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

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

Así en el 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;
}

Answer 2

Otra forma de hacerlo sería la siguiente:

calcula el vector v1 = p2-p1, v2 = p2 -p3. Luego, use la fórmula de producto cruzado: uv = || u || || v || cos (theta)

Answer 3

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

¿Cómo encontramos la señal del sin(a) ? Aquí es donde entra en juego el producto cruzado.

Primero, definamos dos vectores:

v1 = p1-p2
v2 = p3-p2

Esto significa que los dos vectores comienzan en p2 y uno apunta a p1 y el otro apunta a p3 .

El producto cruzado se define como:

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

Ya que tus vectores están en 2d, entonces z1 y z2 son 0 y por lo tanto:

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

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

Ahora, por otro lado, sabemos que:

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

donde ||v|| Es la norma (tamaño) del vector 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 que 180 apuntará hacia abajo. Así que en tu 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 es negativo, entonces es más grande (el valor z fue 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 4

zcross utiliza el signo del vector de producto cruzado (más o menos en la dirección z) para determinar si el ángulo es más o menos de 180 grados, como lo has indicado.