利用旋转卡尺在XNA中寻找凸壳的定向边界框

Question

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

我在维基百科上详细介绍了使用单调链从我的点集推导出一个凸包.

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

但是,我不明白它在最终页面上提到的DOTPR和CROSSPR方法应该返回什么.

我知道如何获得两点的Dot Product和两点的Cross Product,但似乎这些函数应该返回两个边/线段的Dot和Cross Products.我的数学知识无疑是有限的,但这是我对算法所寻求的最佳猜测

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

当我给它一组测试点时,..it返回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是左上角.反转列表似乎就足够了.我也删除了最后的重复点.

完成此过程后,数据将变为:

• Vector2(115,14)
• Vector2(129,0)
• Vector2(131,0)
• Vector2(204,63)
• Vector2(199,68)
• Vector2(150,110)
• Vector2(1,138)
• Vector2(0,138)

当i等于0且j等于3时,该测试在第一个循环上失败.它发现线(115,14)到(204,63)和线(204,63)到(199,68)的交叉积然后发现相同行的点积也是0,因此j和k共享相同的索引.

相比之下,当给出这个测试集时:http: //www.wolframalpha.com/input/？i = polygon +%281%2C1%29%2C%281%P22%29%2C%281%CO2%29%CO2% 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%C22.5%29%2C%283%2C5%29% 2C%285%2C3%29

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

有谁知道我跳过的步骤或在我的代码中看到一些错误,以找到两个线段的点积和交叉积？有没有人在C#之前成功实现过此代码并有一个例子？

Answer 1

我假设 DOTPR 是法向量点积，crosspr 是叉积。点积将返回一个正常数，叉积将返回一个垂直于给定两个向量的向量。（基本向量数学，查看维基百科）

它们实际上在论文中被定义为 DOTPR(i,j) 返回从顶点 i 到 i+1 和 j 到 j+1 的向量的点积。CROSSPR 相同，但具有叉积。