|
2017-12-22 12:47:04
问题: 给定空间点集, 计算与其外形相关的几何参数:
最小(体积)包围盒
最小(体积)包围球
最小(体积)包围椭球
最小(体积)包围圆柱
最小半径包围圆柱
可以再推广一下, 给定空间球(或椭球, 其他空间体), 求其上述参数.
再者, 这些参数之间的关系如何?
这是计算几何中的经典问题, 在各种学科中都有应用. 在化学生物中应用主要是确定分子的形状和大小. 以前在开发分子尺寸大小计算器时, 我也曾遇到这个问题, 当时没有想那么多, 直接用了一种粗略的近似方法. 现在我多看了些资料, 暂且将我看到的罗列一下吧, 供需要的人参考.
精确算法: Joseph O’rourke; Finding Minimal Enclosing Boxes
上述算法的MatLab实现, 很慢: O’Rourke’s algorithm for optimal OBB computation
另一种声称精确的算法, 很快, 提供了论文, 代码以及在线测试: An Exact Algorithm for Finding Minimum Oriented Bounding Boxes
常用算法: Emo Welzl; Smallest Enclosing Disks (Balls And Ellipsoids); Lecture Notes in Computer Science: 359-370; 10.1007/bfb0038202
上述算法的说明及实现: 一种得到点云精确边界球的方法
Kaspar Fischer; Smallest enclosing balls of balls: Combinatorial structure & algorithms
李世林, 李红军; 改进的最小包围球随机增量算法; 图学学报 Vol.37 No.2; 10.11996/JG.j.2095-302X.2016020166
Michael J. Todd, E. Alper Yıldırım; On Khachiyan’s Algorithm for the Computation of Minimum Volume Enclosing Ellipsoids
上述算法MatLab代码
A note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids
Gaertner, Schoenherr; Smallest Enclosing Ellipses Fast And Exact
Jie Tao, Wei Zhang, Chao Lu; Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid
丛伟杰; 求解最小体积闭包椭球问题的积极集算法; 吉林大学学报(理学版) Vol.53 No.2
Michel Petitjean; About The Algebraic Solutions Of Smallest Enclosing Cylinders Problems; AAECC 23(3-4):151-164, 2012; 10.1007/s00200-012-0171-y
上述算法的实现程序
P. K. Agarwal, B. Aronov, M. Sharir; Line Transversals Of Balls And Smallest Enclosing Cylinders In Three Dimensions; Discrete Comput Geom 21(3):373-388, 1999; 10.1007/pl00009427
G. Alistair Watson; Fitting Enclosing Cylinders To Data In R N; Numer Algor 43(2):189-196, 2006; 10.1007/s11075-006-9054-2
Elmar Sch¨omer J¨urgen Sellen; Marek Teichmann; Chee Yap; Smallest Enclosing Cylinders;
Dan Sunday Bounding Containers for Point Sets
李红军, 张晓鹏; 离散点集最小包围圆算法分析与改进; 图学学报 Vol.33 No.2
陶城, 刘军清, 雷邦军, 陈鹏; 跟踪目标的快速椭圆拟合方法
◆本文地址: https://jerkwin.github.io/2017/12/22/点集的几种几何外形参数/, 转载请注明◆
◆评论问题: https://jerkwin.herokuapp.com/category/3/博客, 欢迎留言◆
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-25 21:51
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社