Algorithm for Finding Minimum Volume Oriented Bounding Boxes Based on Convex Hull

被引：0
|
作者：
Hu Z. [1 ]
Qin Q. [1 ]
机构：
[1] School of Software, Central South University, Changsha
来源：
Hunan Daxue Xuebao/Journal of Hunan University Natural Sciences | 2019年 / 46卷 / 02期
基金：
中国国家自然科学基金;
关键词：
Computational geometry; Convex hull; Graph search; Oriented bounding box; Three-dimensional point set;
D O I：
10.16339/j.cnki.hdxbzkb.2019.02.015
中图分类号：
学科分类号：
摘要：
A new method was presented for computing the tight-fitting enclosing minimum volume oriented bounding boxes for constructing the model of complex object point sets in three dimensions. The relationship between the convex hull and its minimum volume oriented bounding box with the smallest volume was analyzed, and four kinds of edge contact types were summarized. The optimal box orientations are uniquely determined by combinations of edges in the convex hull of the input point set. Empirical evidence shows that this process always yields the globally minimum bounding box by volume feature, which concludes that this method provides a good simulation. © 2019, Editorial Department of Journal of Hunan University. All right reserved.
引用
收藏
页码：105 / 111
页数：6
相关论文
共 16 条
  • [1] Shi X.S., Qiao L.H., Zhu Z.W., Algorithm of collision detection based on improved oriented bounding box, Journal of Hunan University(Natural Sciences), 41, 5, pp. 26-31, (2014)
  • [2] Chen H., A method to generate the minimum bounding boxes for shape-arbitrary objects, Journal of Engineering Graphics, 31, 2, pp. 49-53, (2010)
  • [3] O'roukre J., Finding minimal enclosing boxes, International Journal of Computer & Information Sciences, 14, 3, pp. 183-199, (1985)
  • [4] Chen B.S., Ye X.M., An L., Minimum bounding box calculation based on nonlinear principle component analysis, Computer Integrated Manufacturing Systems, 16, 11, pp. 2375-2378, (2010)
  • [5] Dimitrov D., Knauer C., Kriegel K., Et al., Bounds on the quality of the PCA bounding boxes, Computational Geometry Theory & Applications, 42, 8, pp. 772-789, (2009)
  • [6] Barequet G., Har-Peled S., Efficiently approximating the minimum, Journal of Algorithms, 38, 1, pp. 91-109, (2001)
  • [7] Larsson T., Kallberg L., Fast computation of tight fitting oriented bounding boxes, Game Engine Gems, 2, pp. 3-19, (2011)
  • [8] Borckmans P.B., Absil P.A., Oriented bounding box computation using particle swarm optimization, European Symposium on Artificial Neural Networks, (2010)
  • [9] Sun D.Z., Shi Y., Liu H.D., Et al., Solution of minimum bounding box of scattered points based on genetic algorithm, Journal of Beijing University of Aeronautics and Astronautics, 39, 8, pp. 995-998, (2013)
  • [10] Chang C.T., Gorissen B., Melchior S., Fast oriented bounding box optimization on the rotation group SO(3, R), ACM Transactions on Graphics, 30, 5, pp. 1-16, (2011)
12