6

也许这更像是一个数学问题而不是编程问题，但我一直在尝试在 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)
  • 向量 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： 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# 中成功实现过这段代码并有一个例子？

4

2 回答 2

1

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

您的实现CrossProduct似乎是正确的（请参阅Wolfram MathWorld）。但是，PolygonCross我PolygonDot认为您不应该对细分进行规范化。它将影响 和 的返回值的PolygonDot大小PolygonCross。通过删除对您的多余调用，Vector2.Normalize您可以加快代码速度并减少浮点值中的噪声量。但是，规范化与您粘贴的代码的正确性无关，因为它仅将结果与零进行比较。

请注意，您所指的论文假定多边形顶点按逆时针顺序列出（第 5 页，“评论开始”之后的第一段），但您的示例polygon是按顺​​时针顺序定义的。这就是为什么是负数并且你得到和PolygonCross(polygon, 0, 1)相同的值。jk

于 2012-08-14T17:07:29.623 回答
0

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

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

于 2012-08-02T21:08:52.687 回答