xna - 使用旋转卡尺在 XNA 中找到凸包的定向边界框

Question

也许这更像是一个数学问题而不是一个编程问题，但我一直在尝试在 XNA 中实现旋转卡尺算法。

我已经使用维基百科上详述的单调链从我的点集中推导出了一个凸包。

现在，我正在尝试对我的算法进行建模，以在此处找到后找到 OBB:
http://www.cs.purdue.edu/research/technical_reports/1983/TR%2083-463.pdf

但是，我不明白它在最后一页上提到的 DOTPR 和 CROSSPR 方法应该返回什么。

我了解如何获得两点的点积和两点的叉积，但似乎这些函数应该返回两条边/线段的点积和叉积。我的数学知识无疑是有限的，但这是我对算法正在寻找什么的最好猜测

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

请注意，我调用polygon.Reverse 以逆时针顺序放置这些点，如perdue.edu 的技术文档中所示。我的用于查找点集凸包的算法以逆时针顺序生成一个点列表，但这样做是假设 y < 0 高于 y > 0 因为当绘制到屏幕时 0,0 是左上角.反转列表似乎就足够了。我还删除了最后的重复点。

经过这个过程，数据变成:

矢量 2(115, 14)

向量 2(129, 0)

向量 2(131, 0)

Vector2(204, 63)

Vector2(199, 68)

矢量 2(150, 110)

Vector2(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:
http://www.wolframalpha.com/input/?i=polygon+%282.5%2C0.5%29%2C%280.5%2C2.5%29%2C%283%2C5%29%2C%285%2C3%29

我已经阅读了在 http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp 上找到的 C++ 算法但我太密集了，无法完全遵循它。它似乎也与上​​面论文中详述的另一个非常不同。

有谁知道我要跳过哪个步骤或在我的代码中看到一些错误，用于查找两条线段的点积和叉积？有没有人在 C# 中成功实现过这段代码并有一个例子？

Answer 1

点和向量作为数据结构本质上是一回事；两者都包含两个浮点数(如果您在三个维度上工作，则为三个)。所以，当被要求取边的点积时，我想这意味着取边定义的向量的点积。您提供的代码正是这样做的。

您对 CrossProduct 的实现似乎正确(见 Wolfram MathWorld )。然而，在 PolygonCross和 PolygonDot我认为您不应该对分割进行标准化。会影响PolygonDot的返回值的大小和 PolygonCross .通过删除对 Vector2.Normalize 的多余调用您可以加快代码速度并减少浮点值中的噪声量。但是，标准化与您粘贴的代码的正确性无关，因为它只会将结果与零进行比较。

请注意，您引用的论文假设多边形顶点按逆时针顺序列出(第 5 页，“评论开始”之后的第一段)，但您的示例 polygon按顺时针顺序定义。这就是为什么PolygonCross(polygon, 0, 1)是负数，您会得到相同的值 j和 k .