检测角度是否大于180度

Question

我正在研究教授指定的一个问题,而我正在寻找一种方法来检测3点之间的角度是否大于180度,例如:

我想检测alpha是否超过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,这取决于两个矢量是分别具有相同方向还是相反方向.