我正在尝试实现 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)
。
我一定是做错了什么,但我不知道那是什么。
最佳答案
你的错误是dj
函数,可能你误解了dxi
方程或者你没有写出你想要的。
我会尽力解释自己,如果你不明白的地方,请不要犹豫发表评论(我正在编写伪 python 代码,但它应该很容易理解)。
假设我有以下单纯形:
S = Simplex({
1: Point (1, 1) # y1
2: Point (1,-1) # y2
})
我可以立即计算出 2 个增量值:
然后,我可以计算另外 2 个增量值:
希望现在您会开始认识到自己的错误:Δ 值是基于索引的,因此对于维度为 n 的每个单纯形 X,您有 n 个 Δ 值。你的错误之一是假设你可以计算 ΔX0 和 ΔXi 而不管内容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))
关于algorithm - 使用 GJK 的距 ionic 算法找到最接近原点的单纯形上的点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31738959/