Wykrywanie, czy kąt jest większy niż 180 stopni

Question

Pracuję nad problemem, który wyznaczył profesor, i mam problem z wykryciem, czy kąt między 3 punktami jest większy niż 180 stopni, np .:

Chcę wykryć, czy alfa wynosi ponad 180 stopni. W każdym razie, mój profesor ma kod, który rozwiązuje problem, ale ma funkcję zwaną zcross, ale nie wiem dokładnie, jak to działa. Czy ktoś mógłby mi powiedzieć? Jego kod jest tutaj:

#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

Po pierwsze, wiemy, że jeśli sin(a) ma wartość ujemną, kąt jest większy niż 180 stopni.

Jak znaleźć znak sin(a)? Tutaj pojawia się produkt krzyżowy.

Najpierw zdefiniować dwa wektory:

v1 = p1-p2 
v2 = p3-p2 

Oznacza to, że dwa wektory zaczynają się p2 i jednego punktu do p1 i innych punktów do p3.

Krzyż produkt jest zdefiniowany jako:

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

Ponieważ twoi wektory są w 2D, a następnie z1 i z2 to 0, a więc:

(x1, y1, 0) x (x2, y2, 0) = (0, 0, x1y2-x2y1) 

Dlatego nazywają go zcross ponieważ tylko element z produktu ma wartość inną niż 0.

Z drugiej strony, w e wiedzieć, że:

||v1 x v2|| = ||v1|| * ||v2|| * abs(sin(a)) 

gdzie ||v|| jest normą (wielkość) wektora v. Wiemy również, że jeśli kąt a jest mniejszy niż 180, wówczas v1 x v2 będzie skierowany w górę (reguła prawej ręki), natomiast jeśli jest większy niż 180, będzie skierowany w dół. Tak więc w tym szczególnym przypadku:

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

Po prostu, jeżeli wartość oo w v1 x v2 jest pozytywny, wówczas a jest mniejsza niż 180. Jeśli jest negatywna, to jest większy (Wartość oo była x1y2-x2y1). Jeżeli iloczyn krzyżowy wynosi 0, wówczas dwa wektory są równoległe, a kąt wynosi 0 lub 180, w zależności od tego, czy dwa wektory mają odpowiednio ten sam lub przeciwny kierunek.

Answer 2

zcross wykorzystuje znak vector cross product (plus minus w kierunku Z), aby ustalić, czy kąt jest większy lub mniejszy niż 180 stopni, jak pan ujął.

Answer 3

Innym sposobem byłoby zrobić w następujący sposób:

oblicz wektor v1 = p2-p1, p2 v2 = P3. Następnie użyj formuły wielu produktów: u.v = || u || || v || cos (theta)

Answer 4

W 3D znajdź iloczyn krzyżowy wektorów, znajdź minimalną długość dla iloczynu krzyżowego, który jest po prostu znalezieniem najmniejszej liczby x, yiz.

Jeśli najmniejsza wartość jest mniejsza niż 0, kąt wektorów jest ujemny.

Więc w kodzie:

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