3

Point が凸包 (C/C++) の内側/外側または境界 (エッジ) 上にあるかどうかを判断できるアルゴリズムが必要です。

凸包は、ポイント X、Y、整数の配列として記述され、接続は i から i+1 までです。

現在、ここで説明されている巻き数アルゴリズムを使用しています。 http://geomalgorithms.com/a03-_inclusion.html 関数「wn_PnPoly()」です。

ポイントが凸面の境界(エッジ)上に正確にある場合、巻き数アルゴリズムを検出させることは可能ですか? それを行う別のアルゴリズムはありますか？（intで作業する必要があります）。

4

2 に答える 2

8

見つかった解決策:

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;
}
于 2016-06-08T13:17:23.963 に答える
-1

ワインディング数アルゴリズムについては知りませんが、点がエッジの 1 つにあるかどうかを検出するには、凸包のすべてのエッジをループして、次のチェックを実行します。

点 u、v が凸包上の連続する点であり、p が考慮対象の点である場合、

p - u = lambda*(v - u)ここで、lambdaは 0 と 1 の間の任意のスカラーです。

于 2016-06-08T13:15:10.553 に答える