检测角度是否大于180度。

Question

我正在解决教授布置的问题，但我遇到了一个问题，就是寻找一种方法来检测三个点之间的角度是否超过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 ();
}

- Richie Li

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)

由于你的向量是二维的，因此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)

简单来说，如果 v1 x v2 的 z 值为正，则 a 小于 180 度。如果它为负数，则大于 180 度（z 值为 x1y2-x2y1）。如果叉积为 0，则两个向量平行，角度为 0 或 180，这取决于这两个向量是否分别具有相同或相反的方向。

- Shahbaz

---

在二维中，你实际上正在计算“外积”，这是一个比叉积更一般的概念，并且适用于任意维度。可惜的是，它并没有在线性代数入门课程中教授。（公式大多相同，只是没有提到“z”坐标，因此更简单。） - Dietrich Epp

Answer 2

zcross使用向量叉积的符号（在z方向上加减）来确定角度是大于还是小于180度，就像您所说的那样。

- Justin Peel

Answer 3

在三维空间中，找到向量的叉积，找到叉积的最小长度，即找到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;
}

- Frans van Nispen

---

我认为有必要提到，该函数返回的角度在[-180°;180°]之间，而不是[0;360°]之间，运行得非常完美！ - Vertexwahn

Answer 4

另一种方法是这样的：

计算向量v1 = p2-p1，v2 = p2-p3。 然后使用叉积公式：u.v = ||u|| ||v|| cos(theta)。

- grdvnl

---

你如何处理大于180°的角度？ - Vertexwahn

这个符号告诉你它是否大于180度，对吧？ - grdvnl