Обнаружение, если угол больше 180 градусов

Question

Я работаю над проблемой, которую назначил профессор, и у меня возникла проблема с поиском способа определить, превышает ли угол между 3 точками более 180 градусов, например:

Я хочу определить, превышает ли альфа 180 градусов. В любом случае, у моего профессора есть код, который решает проблему, но у него есть функция zcross, но я точно не знаю, как она работает. Кто-нибудь может мне сказать? Его код здесь:

#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

Во-первых, мы знаем, что если sin(a) отрицательно, то угол составляет более 180 градусов.

Как мы находим знак sin(a)?Вот где в игру вступает перекрестное произведение.

Сначала давайте определим два вектора:

v1 = p1-p2
v2 = p3-p2

Это означает, что два вектора начинаются с p2, а один указывает на p1 идругие точки указывают на p3.

Суммарное произведение определяется как:

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

Поскольку ваши векторы находятся в 2d, то z1 и z2 равны 0 и, следовательно:

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

Именно поэтому они называют это zcross , потому что только элемент z продукта имеет значение, отличное от 0.

Теперь, с другой стороны, мызнать, что:

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

, где ||v|| - норма (размер) вектора v.Также мы знаем, что если угол a меньше 180, то v1 x v2 будет указывать вверх (правило правой руки), а если он больше 180, он будет указывать вниз.Итак, в вашем особом случае:

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

Проще говоря, если значение z v1 x v2 положительное, то a меньше 180. Если оно отрицательное, то оно больше (значение zбыло x1y2-x2y1).Если перекрестное произведение равно 0, тогда два вектора параллельны, а угол равен 0 или 180, в зависимости от того, имеют ли два вектора соответственно одинаковое или противоположное направление.

Answer 2

zcross использует знак векторного креста (плюс или минус в направлении z), чтобы определить, больше или меньше угол, как вы сказали.

Answer 3

В 3D найдите перекрестное произведение векторов, найдите минимальную длину для перекрестного произведения, которая в основном просто находит наименьшее число x, y и z.

Если наименьшее значение меньше, чем0, угол векторов отрицателен.

Так в коде:

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 4

Другой способ сделать это будет следующим:

вычисляет вектор v1 = p2-p1, v2 = p2 -p3. Затем используйте формулу кросс-произведения: u.v = || u || || v || соз (тета)