繞線數算法和邊界點/邊凸點

Question

我需要算法可以告訴，如果點位於內部/外部或在凸包的邊界（邊緣）（C/C++）。

凸殼體被描述爲點X，Y，整數的連接，連接從i到i + 1。

目前我正在使用繞組編號算法，這裏描述： http://geomalgorithms.com/a03-_inclusion.html 它的功能是「wn_PnPoly（）」。

如果Point正好位於凸的邊界（邊）上，那麼是否有可能以及如何使繞組數算法檢測？ 有沒有另一種算法來做到這一點？ （需要使用整數）。

Answer 1

我不知道繞數的算法，但檢測點是否位於邊緣的一個，你可以通過凸包的所有邊緣環路，做以下檢查：

如果分U，v是上的凸包的連續點，p是考慮點是否然後，

p - u = lambda*(v - u)其中lambda是實測值0和1

Answer 2

之間的任何標量溶液：

int wn_PnPoly2(Point P, vector<Point> V, int n) 
{ 
    int wn = 0; // the winding number counter 

         // loop through all edges of the polygon 
    for (int i = 0; i<n; i++) { // edge from V[i] to V[i+1] 
     if (V[i].Y <= P.Y) {   // start y <= P.y 
      if (V[i + 1].Y > P.Y)  // an upward crossing 
      { 
       int l = isLeft(V[i], V[i + 1], P); 
       if (l > 0) // P left of edge 
        ++wn;   // have a valid up intersect 
       else if (l == 0) // boundary 
        return 0; 
      } 
     } 
     else {      // start y > P.y (no test needed) 
      if (V[i + 1].Y <= P.Y)  // a downward crossing 
      { 
       int l = isLeft(V[i], V[i + 1], P); 
       if (l < 0) // P right of edge 
        --wn;   // have a valid down intersect 
       else if (l == 0) 
        return 0; 
      } 
     } 
    } 
    return wn; 
}