数学研发论坛

 找回密码
 欢迎注册
查看: 607|回复: 17

[原创] 包覆三点的最小球体体积与表面积

[复制链接]
发表于 2019-5-18 18:53:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
本帖最后由 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] ​​​​

图
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-5-18 18:54:47 | 显示全部楼层
本帖最后由 markfang2050 于 2019-5-18 18:57 编辑

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

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

包覆三点的最小球体体积与表面积
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-19 20:23:57 | 显示全部楼层
3个点是很简单的。由于3点必然共面,我们只要先在这个平面上求出包含三点的最小的圆,然后以圆心为球心,圆半径为球半径做球即可。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-19 20:37:37 | 显示全部楼层
这是计算几何中的老问题问题了,相关研究结果挺丰富的,比如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)。

进一步,这里的空间点可以推广为直径不等的球,即问题推广为求解空间不等直径球集合的最小包围球,也有相关论文的研究,这里就不列举了,自己可以去找找。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-5-19 22:50:15 | 显示全部楼层
kastin 发表于 2019-5-19 20:37
这是计算几何中的老问题问题了,相关研究结果挺丰富的,比如Bernd Gaertner的在1999年发表的经典论文Fast a ...

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-5-19 22:56:24 | 显示全部楼层
此问题我已经用MATLAB编程解决了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-20 09:53:10 | 显示全部楼层
markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。

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

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-20 10:19:43 | 显示全部楼层
markfang2050 发表于 2019-5-19 22:56
此问题我已经用MATLAB编程解决了。

工具不重要,重要的是算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-20 10:32:37 | 显示全部楼层
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"]
复制代码

点评

原来如此,看来是我的MATLAB水平严重退化了  发表于 2019-5-20 17:38
还没注意到有这个函数,看来,近些年MMA也在计算几何领域发力了。查了一下,这个函数是在2016年引入的,功能倒挺全面,最小轴对齐盒和椭球都有,很不错。如果能官方提一下这个内建函数用到的算法就好了。  发表于 2019-5-20 15:47

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
kastin + 3 + 3 + 3 + 3 + 3 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-5-20 15:42:19 | 显示全部楼层
wayne 发表于 2019-5-20 10:32
你的输入数据是啥,怎么我算的跟你的不一样

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

如果按你这个程序里面给的三个点的话,我这里算出的结果是半径6.752958610860873,球心为(4.555, 4.33, 7.285) 相对误差为1.55812e-016,并且程序还发现第1个和第3个点是整个集合(三个点的点集,其实可以更多个点)的支撑集(support set)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-9-19 13:12 , Processed in 0.062770 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表