6

おそらく、これはプログラミングの質問というよりも数学の質問ですが、XNA で回転キャリパー アルゴリズムを実装しようとしています。

ウィキペディアで詳述されているように、モノトーンチェーンを使用して、ポイントセットから凸包を推測しました。

ここで見つかった OBB の後に OBB を見つけるアルゴリズムをモデル化しようとしています: http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

ただし、最終ページで言及されている DOTPR および CROSSPR メソッドが何を返すことになっているのかわかりません。

2 点の内積と 2 点の外積を取得する方法は理解していますが、これらの関数は 2 つのエッジ/線分の内積と外積を返すことになっているようです。私の数学の知識は確かに限られていますが、これはアルゴリズムが何を探しているかについての私の最善の推測です

    public static float PolygonCross(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];

        float crossProduct1 = CrossProduct(segmentA1, segmentB1);
        return crossProduct1;
    }

    public static float CrossProduct(Vector2 v1, Vector2 v2)
    {
        return (v1.X * v2.Y - v1.Y * v2.X);
    }

    public static float PolygonDot(List<Vector2> polygon, int indexA, int indexB)
    {
        var segmentA1 = NextVertice(indexA, polygon) - polygon[indexA];
        var segmentB1 = NextVertice(indexB, polygon) - polygon[indexB];

        float dotProduct = Vector2.Dot(segmentA1, segmentB1);
        return dotProduct;
    }

ただし、コードのこの部分で指示されているようにこれらのメソッドを使用すると...

            while (PolygonDot(polygon, i, j) > 0)
            {
                j = NextIndex(j, polygon);
            }

            if (i == 0)
            {
                k = j;
            }
            while (PolygonCross(polygon, i, k) > 0)
            {
                k = NextIndex(k, polygon);
            }

            if (i == 0)
            {
                m = k;
            }
            while (PolygonDot(polygon, i, m) < 0)
            {
                m = NextIndex(m, polygon);
            }

..ポイントのテスト セットを指定すると、j、k に対して同じインデックスが返されます。

    List<Vector2> polygon = new List<Vector2>() 
        { 
            new Vector2(0, 138),
            new Vector2(1, 138), 
            new Vector2(150, 110), 
            new Vector2(199, 68), 
            new Vector2(204, 63), 
            new Vector2(131, 0), 
            new Vector2(129, 0), 
            new Vector2(115, 14), 
            new Vector2(0, 138), 
        };

perdue.edu の技術文書に示されているように、これらのポイントを反時計回りの順序で配置するために polygon.Reverse を呼び出すことに注意してください。ポイントセットの凸包を見つけるための私のアルゴリズムは、反時計回りの順序でポイントのリストを生成しますが、y < 0 が y > 0 よりも高いと仮定します。 . リストを逆にするだけで十分なようです。最後に重複したポイントも削除します。

このプロセスの後、データは次のようになります。

  • ベクトル 2(115, 14)
  • ベクトル 2(129, 0)
  • ベクトル 2(131, 0)
  • ベクトル 2(204, 63)
  • ベクトル 2(199, 68)
  • ベクトル2(150, 110)
  • ベクトル 2(1, 138)
  • ベクトル2(0, 138)

i が 0 で j が 3 の場合、このテストは最初のループで失敗します。 (115,14) から (204,63) への線分と (204,63) から (199,68) への線分の外積は次のようになります。 ) は 0 です。次に、同じ行の内積も 0 であることがわかります。したがって、j と k は同じインデックスを共有します。

対照的に、このテスト セットが与えられた場合: http://www.wolframalpha.com/input/?i=polygon+%282%2C1%29%2C%281%2C2%29%2C%281%2C3%29%2C% 282%2C4%29%2C%284%2C4%29%2C%285%2C3%29%2C%283%2C1%29

私のコードは、この OBB を正常に返します 。 2C%285%2C3%29

http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cppにある C++ アルゴリズムを読んだことがありますが、あまりにも複雑すぎて完全に従うことができません。また、上記の論文で詳述されている他のものとは大きく異なるようです。

2 つの線分の内積と外積を見つけるために、スキップしているステップを知っている人や、コードにエラーが表示されている人はいますか? 以前にこのコードを C# で正常に実装し、例を持っている人はいますか?

4

2 に答える 2

1

データ構造としての点とベクトルは本質的に同じものです。どちらも 2 つのフロート (3 次元で作業している場合は 3 つ) で構成されています。したがって、エッジの内積を取るように求められた場合、それは、エッジが定義するベクトルの内積を取ることを意味すると思います。あなたが提供したコードはまさにこれを行います。

の実装はCrossProduct正しいようです( Wolfram MathWorldを参照)。ただし、セグメントを正規化するべきではないPolygonCrossとPolygonDot思います。と の戻り値の大きさに影響しPolygonDotますPolygonCross。の余分な呼び出しを削除することでVector2.Normalize、コードを高速化し、浮動小数点値のノイズの量を減らすことができます。ただし、正規化は結果をゼロと比較するだけなので、貼り付けたコードの正確性には関係ありません。

参照する論文では、ポリゴンの頂点が反時計回りの順序でリストされていると想定していますが (5 ページ、「コメントの開始」の後の最初の段落)、例polygonは時計回りの順序で定義されていることに注意してください。PolygonCross(polygon, 0, 1)が負であり、 と で同じ値が得られるのはjそのためkです。

于 2012-08-14T17:07:29.623 に答える
0

DOTPR は通常のベクトル内積であり、crosspr は外積であると仮定します。dotproduct は通常の数値を返し、crossproduct は指定された 2 つのベクトルに垂直なベクトルを返します。(基本的なベクトル計算、ウィキペディアを確認してください)

DOTPR(i,j) は、頂点 i から i+1 および j から j+1 までのベクトルのドット積を返すため、これらは実際には論文で定義されています。CROSSPR と同じですが、交差積があります。

于 2012-08-02T21:08:52.687 に答える