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 条

[11] Freeman H., Shapira R., Determining the minimum-area encasing rectangle for an arbitrary closed curve, Communications of the ACM, 18, 7, pp. 409-413, (1975)
[12] Barber C.B., Dobkin D.P., Huhdanpaa H., The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software, 22, 4, pp. 469-483, (1996)
[13] Imai H., Iri M., Polygonal approximations of a curve, Computational Morphology, 6, 1, pp. 71-86, (2014)
[14] Li R.Z., Yang M., Liu Y.Y., Et al., An uniform simplification algorithm for scattered point cloud, Acta Optica Sinica, 37, 7, pp. 89-97, (2017)
[15] A C++ library for linear algebra and geometry manipulation for computer graphics
[16] 3D meshes research database, (2008)

← 1 2 →