用N维空间中3点的最小距离计算等距点 [英] Calculate equidistant point with minimal distance from 3 points in N-dimensional space

问题描述

我试图在任意维度上编写 Ritter的包围球算法 ，我被困在创造一个球体的部分上，这个球体在其边缘有3个给定的点，或者换句话说，就是一个在N维空间中由3个点定义的球体。

这个球体的中心是距离（定义）3个点的最小距离等距点。

我知道如何在2 -D（由3个点定义的三角形的外接中心），并且我已经看到了3D的一些向量计算，但我不知道ND的最佳方法是什么，甚至是可能的。

（我也很感激任何关于ND中最小边界球计算的其他建议，以防万一我走错了方向。）

通缉点 p

code>是相同半径的三个超球体之间的交点 r 其中超球体的中心是你的点 p0，p1， p2 和半径 r 是所有可能解决方案中的最小值。在 nD 中是任意点，定义为（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 =方程式和 n + 1 未知数并解决它。 $ b

[notes] p>

为了简化处理，您可以使用以下形式的公式：

 （p.xi-p0.xi）^ 2 = r ^ 2 
  

并使用 sqrt（r ^ 2），只有找到解决方案后（忽略负半径）。

可能的方法：

您可以计算点 p0，p1，p2 所在的平面所以只需在这个平面内找到 u，v 这些点的坐标。然后在 2D 上在（u，v）坐标中解决问题，然后将找到的解决方案转换为（u，v ）返回您的 nD 空格。 $ b

  n =（ P1-P0）×（P2-P0）; // x是交叉乘积
 u =（p1-p0）; U / = | U |; 
 v = u x n; V / = | V |; // x是交叉产品
  

如果我的内存为我服务，那么转换 nD - >

  P0 =（0,0）; 
 P1 =（| p1-p0 |，0）; 
 P2 =（dot（p2-p0，u），dot（p2-p0，v））; 
  

其中 P0，P1，P2 点对应于 p0，p1，p2 的平面的（u，v）坐标系中的点 2D



在 nD 空间中。



转换返回是这样完成的：

  p =（Pu * u）+（Pv * v）; 
  




I'm trying to code the Ritter's bounding sphere algorithm in arbitrary dimensions, and I'm stuck on the part of creating a sphere which would have 3 given points on it's edge, or in other words, a sphere which would be defined by 3 points in N-dimensional space.

That sphere's center would be the minimal-distance equidistant point from the (defining) 3 points.

I know how to solve it in 2-D (circumcenter of a triangle defined by 3 points), and I've seen some vector calculations for 3D, but I don't know what the best method would be for N-D, and if it's even possible.

(I'd also appreciate any other advice about the smallest bounding sphere calculations in ND, in case I'm going in the wrong direction.)

解决方案

so if I get it right:

Wanted point p is intersection between 3 hyper-spheres of the same radius r where the centers of hyper-spheres are your points p0,p1,p2 and radius r is minimum of all possible solutions. In n-D is arbitrary point defined as (x1,x2,x3,...xn)

so solve following equations:

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

where p,r are unknowns and p0,p1,p2 are knowns. This lead to 3*n equations and n+1 unknowns. So get all the nonzero r solutions and select the minimal. To compute correctly chose some non trivial equation (0=r) from each sphere to form system of n+1 =equations and n+1 unknowns and solve it.

[notes]

To ease up the processing you can have your equations in this form:

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

and use sqrt(r^2) only after solution is found (ignoring negative radius).

there is also another simpler approach possible:

You can compute the plane in which the points p0,p1,p2 lies so just find u,v coordinates of these points inside this plane. Then solve your problem in 2D on (u,v) coordinates and after that convert found solution form (u,v) back to your n-D space.

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

if memory of mine serves me well then conversion n-D -> u,v is done like this:

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

where P0,P1,P2 are 2D points in (u,v) coordinate system of the plane corresponding to points p0,p1,p2 in n-D space.

conversion back is done like this:

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

这篇关于用N维空间中3点的最小距离计算等距点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！