检测角度是否超过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开始。

跨产品的定义是：由于您的载体是2D

(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.

现在，另一方面，w Ë知道：

||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更小。如果是否定的，那么它的大（z值是x1y2-x2y1）。如果叉积为0，则两个矢量平行，角度为0或180，这取决于两个矢量分别具有相同还是相反的方向。

Answer 2

ZCROSS使用vector cross product（z方向正或负）的符号，以确定如果角度大于或小于180度，因为你已经把它。

Answer 3

另一种方法将是如下：

计算矢量V1 = P2-P1，V2 = P2-P3。 然后，使用叉积公式：u。v = || u || || v || cos（θ）

Answer 4

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