c - 检测角度是否大于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) 的符号？这就是叉积发挥作用的地方。

首先，让我们定义两个 vector :

v1 = p1-p2
v2 = p3-p2

这意味着两个 vector 从 p2 开始，一个指向 p1，另一个指向 p3。

叉积定义为:

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

因为你的 vector 是二维的，所以 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|| 是 vector v 的范数(大小)。此外，我们知道如果角度 a 小于 180，则 v1 x v2 将指向上方(右手法则)，而如果大于 180，则它将指向上方指向下方。所以在你的特殊情况下:

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

简单的说，如果v1 x v2的z值为正数，那么a小于180，如果为负数，则更大(Z值是 x1y2-x2y1)。如果叉积为 0，则两个 vector 平行，夹角为 0 或 180，具体取决于两个 vector 的方向相同还是相反。