Erkennen, ob der Winkel mehr als 180 Grad beträgt

Ich arbeite an einem Problem, das der Professor zugewiesen hat, und ich habe ein Problem damit, nach einer Möglichkeit zu suchen, um festzustellen, ob der Winkel zwischen 3 Punkten mehr als 180 Grad beträgt, z.

Ich möchte erkennen, ob Alpha mehr als 180 Grad beträgt. Wie auch immer, mein Professor hat einen Code, der das Problem löst, aber er hat eine Funktion namens zcross, aber ich weiß nicht genau, wie sie funktioniert. Könnte mir jemand sagen? Sein Code ist hier:

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

Erstens wissen wir, dass wenn sin(a) negativ ist, dann beträgt der Winkel mehr als 180 Grad.

Wie finden wir das Zeichen von sin(a)? Hier kommt das Kreuzprodukt ins Spiel.

Lassen Sie uns zunächst zwei Vektoren definieren:

v1 = p1-p2
v2 = p3-p2

Das bedeutet, dass die beiden Vektoren bei beginnen p2 und man zeigt auf p1 und die anderen zeigen auf p3.

Kreuzprodukt ist definiert als:

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

Da Ihre Vektoren dann in 2d sind z1 und z2 sind 0 und somit:

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

Deshalb nennen sie es zkreuz weil nur das z-Element des Produkts einen anderen Wert als 0 hat.

Andererseits wissen wir jetzt, dass:

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

wo ||v|| ist die Norm (Größe) des Vektors v. Außerdem wissen wir, dass, wenn der Winkel a ist dann kleiner als 180 v1 x v2 zeigt nach oben (Regel für die rechte Hand), wenn es größer als 180 ist, zeigt es nach unten. Also in deinem speziellen Fall:

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

Einfach ausgedrückt, wenn der z-Wert von v1 x v2 ist dann positiv a ist kleiner als 180. Wenn es negativ ist, dann ist es größer (Der z-Wert war x1y2-x2y1). Wenn das Kreuzprodukt 0 ist, dann sind die beiden Vektoren parallel und der Winkel ist entweder 0 oder 180, je nachdem, ob die beiden Vektoren jeweils dieselbe oder entgegengesetzte Richtung haben.

zcross verwendet das Zeichen des Vektorkreuzprodukt (plus oder minus in z-Richtung), um festzustellen, ob der Winkel mehr oder weniger als 180 Grad beträgt, wie Sie es ausgedrückt haben.

Finden Sie in 3D das Kreuzprodukt der Vektoren, finden Sie die minimale Länge für das Kreuzprodukt, was im Grunde nur das Finden der kleinsten Anzahl von x, y und z ist.

Wenn der kleinste Wert kleiner als 0 ist, ist der Winkel der Vektoren negativ.

Also im Code:

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

Eine andere Möglichkeit wäre wie folgt:

Berechne den Vektor v1=p2-p1, v2 = p2 -p3. Verwenden Sie dann die Kreuzproduktformel: uv = ||u|| ||v|| cos(theta)