仓库源文，站点原文

layout: post title: 点集的几种几何外形参数 categories:

问题: 给定空间点集, 计算与其外形相关的几何参数:

可以再推广一下, 给定空间球(或椭球, 其他空间体), 求其上述参数.

再者, 这些参数之间的关系如何?

这是计算几何中的经典问题, 在各种学科中都有应用. 在化学生物中应用主要是确定分子的形状和大小. 以前在开发分子尺寸大小计算器时, 我也曾遇到这个问题, 当时没有想那么多, 直接用了一种粗略的近似方法. 现在我多看了些资料, 暂且将我看到的罗列一下吧, 供需要的人参考.

最小包围盒

精确算法: 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

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;