algorithm - 使用 GJK 的距 ionic 算法找到最接近原点的单纯形上的点

Question

我正在尝试实现 Gilbert–Johnson–Keerthi distance algorithm (GJK)，但我在使用“距 ionic 算法”(也称为“约翰逊算法”)时遇到问题，该算法用于确定最接近原点的单纯形上的点。我得到的结果不正确，但我在我的代码中找不到任何错误，所以问题一定出在我对算法的解释上。

在 Johnson 算法中(如 Gino van den Bergen 的书 Collision Detection in Interactive 3D Environments 中所述)，单纯形 仿射包上的点 X = {yi : i ∈ Ix 最接近原点的是:

其中 Δi^X 值是按照 X 的基数递增的顺序递归确定的:

... Δ^X 由下式给出:

对于二维，我使用以下方法找到离原点最近的点:

Point ClosestPointToOrigin(Simplex simplex)
{
    float dx = 0;
    for (int i = 0; i < simplex.size(); ++i)
        dx += dj(simplex, i);

    Point closest_point(0,0);
    for (int i = 0; i < simplex.size(); ++i)
        closest_point += dj(simplex, i) / dx * simplex[i];

    return closest_point;
}

其中 Δi 值由以下因素决定:

float dj(Simplex simplex, int j)
{
    if (j == 0)
    {
        return 1;
    }
    else
    {
        float d = 0;

        for (int i = 0; i < j; ++i)
            d += dj(simplex, i) * (simplex[0] - simplex[j]).dotProduct(simplex[i]);

        return d;
    }
}

对于单纯形 X = {y1, y2} 其中 y1 = (1,1), y2 = (1,-1)，上面的代码返回 (1.0, -0.333333)，而最近的点实际上是 (1, 0)。

我一定是做错了什么，但我不知道那是什么。

Answer 1

你的错误是dj函数，可能你误解了dxi方程或者你没有写出你想要的。

我会尽力解释自己，如果你不明白的地方，请不要犹豫发表评论(我正在编写伪 python 代码，但它应该很容易理解)。

假设我有以下单纯形:

S  = Simplex({
    1: Point (1, 1)  # y1
    2: Point (1,-1)  # y2
})

我可以立即计算出 2 个增量值:

然后，我可以计算另外 2 个增量值:

希望现在您会开始认识到自己的错误:Δ 值是基于索引的，因此对于维度为 n 的每个单纯形 X，您有 n 个 Δ 值。你的错误之一是假设你可以计算 Δ^X₀ 和 Δ^X_i 而不管内容X，这是错误的。

现在是最后一个Δ:

注意:

一旦你在这里:

这是一段用Python写的代码，如果你看不懂，我会试着用你看得懂的语言写一段:

import numpy


class Point(numpy.ndarray):
    def __new__(cls, x, y):
        return numpy.asarray([x, y]).astype(float).view(cls)

    def __str__(self):
        return repr(self)

    def __repr__(self):
        return "Point ({}, {})".format(self.x, self.y)

    x = property(fget=lambda s: s[0])
    y = property(fget=lambda s: s[1])


class Simplex(dict):
    def __init__(self, points):
        super(Simplex, self).__init__(enumerate(points))

    def __str__(self):
        return repr(self)

    def __repr__(self):
        return "Simplex <" + dict.__repr__(self) + ">"


def closest_point(s):
    dx = sum(dj(s, i) for i in range(len(s)))
    return sum(dj(s, i) / dx * v for i, v in s.items())


def dj(s, j):
    if len(s) == 0 or (len(s) == 1 and j not in s):
        print(s, j)
        raise ValueError()
    if len(s) == 1:
        return 1
    ts = s.copy()
    yj = s[j]
    del ts[j]
    return sum(
        dj(ts, i) * (ts[list(ts.keys())[0]] - yj).dot(v) 
        for i, v in ts.items()
    )


S = Simplex([Point(1, 1), Point(1, -1)])

print(closest_point(S))