geometry - 计算N维空间3个点距离最小的等距点

Question

我正在尝试对 Ritter's bounding sphere algorithm 进行编码在任意维度上，我被困在创建一个球体的部分，该球体的边缘有 3 个给定点，或者换句话说，一个球体将由 N 维空间中的 3 个点定义。

该球体的中心将是距(定义)3 个点的最小距离等距点。

我知道如何在 2-D(由 3 个点定义的三角形的外接圆心)中解决它，并且我已经看到一些 3D 的矢量计算，但我不知道 N-D 的最佳方法是什么，如果可能的话。

(对于 ND 中最小包围球计算的任何其他建议，我也很感激，以防我走错方向。)

Answer 1

所以如果我做对了:

想要的点 p 是 3 个相同半径 r 超球体的交点，超球体的中心是你的点 p0,p1,p2 和 radius r 是所有可能解决方案中的最小值。 n-D 中的任意点定义为 (x1,x2,x3,...xn)

所以求解以下方程:

|p-p0|=r
|p-p1|=r
|p-p2|=r

其中 p,r 是未知数，p0,p1,p2 是已知数。这导致 3*n 方程和 n+1 未知数。因此，获取所有非零 r 解决方案并选择最小的。为了正确计算，从每个球体中选择了一些非平凡方程 (0=r) 以形成 n+1 =equations 和 n+1 的系统未知数并求解。

[注释]

为了简化处理，您可以使用以下形式的方程式:

(p.xi-p0.xi)^2=r^2

只有在找到解后才使用 sqrt(r^2)(忽略负半径)。

还有另一种更简单的方法:

您可以计算点 p0,p1,p2 所在的平面，因此只需找到该平面内这些点的 u,v 坐标即可。然后在 (u,v) 坐标上以 2D 解决您的问题，然后将找到的解决方案形式 (u,v) 转换回您的 n维空间。

n=(p1-p0)x(p2-p0); // x is cross product
u=(p1-p0); u/=|u|;
v=u x n; v/=|v|; // x is cross product

如果我的内存对我有用，那么转换 n-D -> u,v 是这样完成的:

P0=(0,0);
P1=(|p1-p0|,0);
P2=(dot(p2-p0,u),dot(p2-p0,v));

其中P0,P1,P2是(u,v)坐标系中的二维点对应的平面n-D 空间中的 p0,p1,p2。

转换回来是这样完成的:

p=(P.u*u)+(P.v*v);