包覆三点的最小球体体积与表面积

markfang2050

三维空间，随机三点坐标已知，求包覆三点的最小球体体积与表面积=？
[偷笑]
test:
[0.12,1.33.3.17;
1.31,3.07,6.39;
8.99,7.33,11.4] ​​​​

markfang2050

三点或更多点随机给出，计算包覆所有点的最小球体体积。

mathe

3个点是很简单的。由于3点必然共面，我们只要先在这个平面上求出包含三点的最小的圆，然后以圆心为球心，圆半径为球半径做球即可。

kastin

这是计算几何中的老问题问题了，相关研究结果挺丰富的，比如Bernd Gaertner的在1999年发表的经典论文Fast and Robust Smallest Enclosing Balls（代码见 https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html），以及Emo Welzl的论文Smallest enclosing disks (balls and ellipsoids)
另外这个问题还可以继续扩展到更高维（注意，不是数十数百，而是上千维，这时普通算法效率就显得低下了，要专门设计新的算法提高效率，见 Kaspar Fischer 等人的论文 Fast Smallest-Enclosing-Ball Computation in High Dimensions）。

进一步，这里的空间点可以推广为直径不等的球，即问题推广为求解空间不等直径球集合的最小包围球，也有相关论文的研究，这里就不列举了，自己可以去找找。

markfang2050

kastin 发表于 2019-5-19 20:37
这是计算几何中的老问题问题了，相关研究结果挺丰富的，比如Bernd Gaertner的在1999年发表的经典论文Fast a ...

markfang2050

此问题我已经用MATLAB编程解决了。

kastin

markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。

2013年我曾编写过这个问题的MATLAB程序，现在拿来测试一下结果：
对于上面的三个点，所求最小包围球的球心位于 `(1.645,3.85,10.195)`，半径为 `3.198319871432500`，结果的相对精度为 `2.38775\times 10^{-16}`. 看一下你算得结果是不是一样？

wayne

markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。

工具不重要，重要的是算法

wayne

kastin 发表于 2019-5-20 09:53
2013年我曾编写过这个问题的MATLAB程序，现在拿来测试一下结果：
对于上面的三个点，所求最小包围球的球 ...

你的输入数据是啥，怎么我算的跟你的不一样

1. pts={{0.12,1.33,3.17},
   
2. {1.31,3.07,6.39},
   
3. {8.99,7.33,11.4}};
   
4. ans=BoundingRegion[pts,"MinBall"]

复制代码

kastin

wayne 发表于 2019-5-20 10:32
你的输入数据是啥，怎么我算的跟你的不一样

你算的也没问题，因为我用的是你给的矩阵的转置。主要是楼主也没说按列还是按行算三维坐标，因为matlab里面习惯按列来的，所以我就事先加了转置。

如果按你这个程序里面给的三个点的话，我这里算出的结果是半径6.752958610860873，球心为(4.555, 4.33, 7.285) 相对误差为1.55812e-016，并且程序还发现第1个和第3个点是整个集合（三个点的点集，其实可以更多个点）的支撑集（support set）。