包覆三点的最小球体体积与表面积
本帖最后由 markfang2050 于 2019-5-18 18:55 编辑三维空间，随机三点坐标已知，求包覆三点的最小球体体积与表面积=？
[偷笑]
test:
[0.12,1.33.3.17;
1.31,3.07,6.39;
8.99,7.33,11.4] 本帖最后由 markfang2050 于 2019-5-18 18:57 编辑
三点或更多点随机给出，计算包覆所有点的最小球体体积。
3个点是很简单的。由于3点必然共面，我们只要先在这个平面上求出包含三点的最小的圆，然后以圆心为球心，圆半径为球半径做球即可。 这是计算几何中的老问题问题了，相关研究结果挺丰富的，比如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）。
进一步，这里的空间点可以推广为直径不等的球，即问题推广为求解空间不等直径球集合的最小包围球，也有相关论文的研究，这里就不列举了，自己可以去找找。 kastin 发表于 2019-5-19 20:37
这是计算几何中的老问题问题了，相关研究结果挺丰富的，比如Bernd Gaertner的在1999年发表的经典论文Fast a ...
:b: 此问题我已经用MATLAB编程解决了。 markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。
2013年我曾编写过这个问题的MATLAB程序，现在拿来测试一下结果：
对于上面的三个点，所求最小包围球的球心位于 `(1.645,3.85,10.195)`，半径为 `3.198319871432500`，结果的相对精度为 `2.38775\times 10^{-16}`. 看一下你算得结果是不是一样？
markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。
工具不重要，重要的是算法 kastin 发表于 2019-5-20 09:53
2013年我曾编写过这个问题的MATLAB程序，现在拿来测试一下结果：
对于上面的三个点，所求最小包围球的球 ...
你的输入数据是啥，怎么我算的跟你的不一样
pts={{0.12,1.33,3.17},
{1.31,3.07,6.39},
{8.99,7.33,11.4}};
ans=BoundingRegion
wayne 发表于 2019-5-20 10:32
你的输入数据是啥，怎么我算的跟你的不一样
你算的也没问题，因为我用的是你给的矩阵的转置。主要是楼主也没说按列还是按行算三维坐标，因为matlab里面习惯按列来的，所以我就事先加了转置。
如果按你这个程序里面给的三个点的话，我这里算出的结果是半径6.752958610860873，球心为(4.555, 4.33, 7.285) 相对误差为1.55812e-016，并且程序还发现第1个和第3个点是整个集合（三个点的点集，其实可以更多个点）的支撑集（support set）。
页:
[1]
2