檢測角度是否超過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; 
}