Issue 
Int. J. Metrol. Qual. Eng.
Volume 11, 2020



Article Number  9  
Number of page(s)  11  
DOI  https://doi.org/10.1051/ijmqe/2020007  
Published online  22 October 2020 
Research Article
Estimation of minimum volume of bounding box for geometrical metrology
Department of Mechanical and Industrial Engineering, NTNU, NO7491 Trondheim, Norway
^{*} Corresponding author: petr.chelishchev@ntnu.no
Received:
3
April
2020
Accepted:
24
September
2020
This paper presents algorithms for estimating the minimum volume bounding box based on a threedimensional point set measured by a coordinate measuring machine. A new algorithm, which calculates the minimum volume with high accuracy and reduced number of computations, is developed. The algorithm is based on the convex hull operation and established theories about a minimum bounding box circumscribing a convex polyhedron. The new algorithm includes a preprocessing operation that removes convex polyhedron faces located near the edges of the measured object. As showed in the paper, the solution of the minimum bonding box is not based on faces located near the edges; therefore, we can save computation time by excluding them from the convex polyhedron data set. The algorithms have been demonstrated on physical objects measured by a coordinate measuring machine, and on theoretical 3D models. The results show that the algorithm can be used when high accuracy is required, for example in calibration of reference standards.
Key words: Minimum volume bounding box / minimum bounding rectangle / convex polyhedron / CMM
© P. Chelishchev and K. Sørby, published by EDP Sciences, 2020
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1 Introduction
In various applications, it can be useful to circumscribe a given set of threedimension coordinate points by an ideal shape rectangular parallelepiped. It was suggested by Dupuis [1] to use the term cuboid when referring to a rectangular parallelepiped. However, in the literature of the computational geometry, the term box is commonly associated with the rectangular parallelepiped. In this text, we use the term side for the bounding box face. This term may be also used while referring to the physical cuboid object side. The term face is mainly used for the inscribed convex polyhedron faces, which are the product of 3D convex hull operation. All six sides (faces) of the box are rectangles and each side is parallel with the opposite side and orthogonal with the other four adjacent sides. These four adjacent sides comprise a “closed loop”. For example, the Top side has a “closed loop” of adjacent sides that consists of: Front, Left, Right, and Back. The opposite, Bottom side has the same “closed loop” of adjacent sides as the Top side.
An estimation of the minimal volume bounding box (MVBB) often includes an estimation of the minimal area bounding rectangle (MABR). Both problems are commonly used in computer graphics (e.g. collision detection, optimal layout detection etc.), image processing, medicine (e.g. brachytherapy), metrology, automatic tariffing in goodstraffic and many other applications. Together with other association criteria (e.g. minimum zone, least squares), the minimum volume criterion can be applied for estimation of the flatness deviation of mechanical parts in industry [2]. Depending on an application, the MVBB algorithm may be optimized either for computation time or for measurement accuracy.
Based on the proposals of Shamos [3], Freeman and Shapira [4], Toussaint presented an elegant unambiguous MABR solution in [5]. This exact solution of the MABR problem has O(n ^{2}) computing time with the use of the rotating caliper algorithm for npoint set in ℝ ^{2}, and O(n) time with the use of two pairs of rotating calipers orthogonal to each other. A number of approximation algorithms and heuristic alternatives are suggested to solve the twodimension problem. Among them, the searching algorithms based on the Rtree data structures [6–8] and the principle components [9,10].
The most exact solution of the MVBB problem for npoint set in ℝ ^{3} with computation time O(n ^{3}) was provided by O'Rourke [11], which remains the stateoftheart so far. Alternative approximation algorithms have been developed to reduce the computation time. Bespamyatnikh and Segal [12] suggested an efficient O(n ^{2}) approximation algorithm. A search based on Powell's quadratic convergent method was proposed by Lahanas et al. [13]. Later, Barequet and HarPeled [14] presented an approximating algorithm with O(n + 1/ϵ ^{4.5}) computation time, and a simplified version with O(nlogn + n/ϵ ^{3}), where 0 < ϵ ≤ 1. Recently, Dimitrov et al. developed a faster algorithm based on the discrete and the continuous versions of principal component analysis (PCA) [10,15]. The continuous version guarantees a constant approximation factor but it is still limited by O(nlogn) − time required for computation of a convex hull. The commonly used solutions for MABR and MVBB are based on the convex hull operation [3,16], in order to reduce the number of considered points and avoid redundant computation.
Some approximation algorithms may provide a large systematic error. The majority of approaches presented above are mainly focused on reducing the computation time, but at the expense of accuracy. In this paper, we consider calculation of the minimum bounding box on reference standards used for calibration of dimensional measuring systems; hence, the accuracy must be ensured. The elegant approach provided by O'Rourke is the accurate solution, but it does not take into account some metrological issues related to the discrete point measurement with CMM, which are discussed below.
The physical edges (denoted by 1 in Fig. 1a) of the cuboid object are typically not measured and there is always a distance between the edges and the measured points. As a result, there is an intermediate space between the measured points on all pairs of the adjacent sides (e.g. side 2 and side 3, side 3 and side 4 in Fig. 1a) of the cuboid object. This intermediate space is transformed into a large number of the convex polyhedron faces after appliance of the convex hull operation. Such newly constructed faces provide acute angles and look similar to “chamfer” faces (denoted by 5 in Fig. 1b). These faces cut off the physical cuboid object and they will lead to unnecessary computation in the O'Rourke algorithm. Obviously, these “chamfer” faces cannot be a part of the minimum bounding box solution and these faces should be excluded from the algorithm.
In this paper, we deal with the minimum bounding box problem for physical objects with an actual shape close to the perfectly rectangular bounding box. The proposed algorithms for estimation of MVBB take into account the effect of the “chamfer” faces. The most accurate algorithm searches for the minimum solution according to the conditions defined by two theorems related to the MABR and the MVBB problems presented in Section 2. A detailed overview of the three conventional geometrical algorithms suggested by the author are given in Section 3. Implementation of the methods is presented in Section 4 with description of the experimental setup and computational results.
Fig. 1
An example of the metrological issue: (a) a cuboid object with CMM measured points; (b) an example of the convex polyhedron with the chamfer faces after convexhull operation; 1–edges; 2–left side; 3–top side; 4–front side; 5–“chamfer” polyhedron faces; 6–ordinary polyhedron faces. 
2 Theoretical background
The solution of the threedimension MVBB problem involves the twodimension case. After the orientation of one side of the bounding box is locked in the MVBB algorithm, all points are projected onto the xyplane, and the orientations of other adjacent sides of the bounding box can be found by the MABR algorithm as the twodimension problem.
2.1 Minimumarea bounding rectangle
The earliest known solution of the MABR problem was presented by Freeman and Shapira [4]. They presented the following theorem, which is the basis for minimum bounding rectangle algorithms: The rectangle of minimum area enclosing a convex polygon has a side collinear with one of the edges of the polygon.
The MABR solution is based on the 2D convex hull operation [3], which is applied as the first step. In the second step, we search for the minimumarea bounding rectangle circumscribing the convex polygon constructed by the convex hull algorithm in the first step. The theorem mentioned above limits the number of bounding rectangles that are candidates for the minimumarea bounding rectangle.
2.2 Minimumvolume bounding box
The second theorem presented here was formulated and proved for the MVBB problem by O'Rourke [11]: A box of minimal volume circumscribing a convex polyhedron must have at least two adjacent sides flush with edges of the polyhedron.
It is not necessary that one of the sides of the bounding box is coplanar with one of the faces of the convex polyhedron. In fact, the bounding box with minimal volume circumscribing a regular tetrahedron has all six sides coplanar with the tetrahedron edges without flushing with any tetrahedron faces (Fig. 2a).
However, in practise (to be shown in the experimental part, Sect. 4.2), the minimal solution may also correspond to the case when one or more sides of the bounding box are coplanar with faces of the convex polyhedron. An example, where each side of the bounding box is coplanar with face of the polyhedron (Model B) is shown in Figure 2b. The vertex coordinates of this convex polyhedron are given as the Model B in Table 1. The Model B was derived from the reference Model A. The Model A is based on a regular cube with edge length 1 and chamfers with distances 0.1 × 0.1 (normalized units). So that each side of the Model A is given by five points. There is one point in the middle of a face, and there are four points in the corners of the face. The modified coordinates of Model B and Model C relative to the Model A are marked by bold text in Table 1. Figure 2c shows the other example, where two adjacent sides of MVBB are coplanar only with two edges 1 and 2 of the convex polyhedron. Optimization curves for the minimum volume versus an orientation angle between a bounding box side and a face of the Model C are illustrated in Figure 3. The relationship of the minimal volume versus the orientation angle of the Models may appear either linear (Fig. 3a) or nonlinear (Fig. 3b). The beginning of both curves corresponds to the volume where one side of the bounding box is coplanar with the polyhedron face. The end of the curves corresponds to the volume where the same side of the bounding box is coplanar with its adjacent polyhedron face. The other points on the curves correspond to the volume for orientation angles where one side of the bounding box coincides with the polyhedron edge.
Fig. 2
Examples of convex polyhedrons: (a) a regular tetrahedron with edge length circumscribed by minimal box with edge length 1; (b) convex polyhedron related to Model B; (c) convex polyhedron related to Model C; 1–the edge is flush with the Top side; 2–the edge is flush with the Left side. 
The coordinates of points for the theoretical models (in normalized units).
Fig. 3
The optimization functions of volume versus orientation angle between two faces (Model C): (a) around the edge 2 on the Left side (small angle); (b) around the edge 1 on the Top side (large angle). 
3 Computation methods
In the following sections, three methods for finding the Minimum Volume Bounding Box (MVBB) are considered. The methods are denoted as the “side” method (MVBBS), the “face” method (MVBBF) and the “edges” method (MVBBE). All three methods differ from each other by accuracy, complexity and hence the computation time.
All the three methods utilizes the MABR algorithm [4]. Two of the methods (“face”, “edges”) include the specific data preprocessing algorithm (Sect. 3.3), which distinguishes these methods from other known methods. Only the MVBBE method completely satisfies to both theorems given in Sections 2.1 and 2.2, and therefore it can be used as the reference for the other alternative methods.
3.1 The minimum area bounding rectangle (MABR) algorithm
The MABR algorithm is based on 2D convex hull operation [3]. After a convex polygon P is constructed, the angles θ _{ i } between the polygon edges and the xaxis are calculated as follows:(1)where atan 2 is the fourquadrant tangent inverse function. The polygon vertices (p _{1}, p _{2}, … , p _{ n }) are rotated in such way that the first convex polygon edge e _{1} is parallel with the xaxis. Then at least three other points p _{ i } with extreme (x, y) coordinates are defined − two in orthogonal direction to the xaxis (y _{max}, y _{min}), and another two coordinates in orthogonal direction to the yaxis (x _{min}, x _{max}). The polygon vertices continues rotating with angle −θ _{ i } in clockwise direction from one edge e _{ i } to another e _{ i+1} until all polygon edges are checked. The twodimension rotation matrix is a follows:(2)
A new rectangle area A _{ i } is calculated for each rotation. The corresponding rectangle length L _{ i } = x _{max} − x _{min} and width W _{ i } = y _{max} − y _{min} are updated, when a new minimum area A _{min} = L _{ i } ⋅ W _{ i } is obtained. An example of the MABR is shown in Figure 4. One of the edges of the polygon is collinear with one of the sides of the bounding rectangle. The algorithm also checks whether the solution is unique or not.
Fig. 4
The MABR of a convex polygon based on 2D point set. 
3.2 The minimum volume bounding box side (MVBBS) Method
This MVBBS approximation method is well known and often used in practice. It is fast and straightforward, based on an assumption that the test object has one perfectly flat side e.g. Bottom, which is aligned with the support surface (Z _{min}). Such assumption allows a substantial simplification, both the measurement procedure and the computation procedure. However, because of the assumption of one perfectly flat side, the estimated minimal volume by this method can be not accurate. Groen et al. [17] developed an operational automatic system for measurement of parcels and suitcases on a conveyor belt based on this principle. The flowchart of the MVBBS method is illustrated in Figure 5.
The principle of this method is to define the height as H _{min} = Z _{max} − Z _{min} and the smallest area A _{min} of the bounding rectangle for the xyprojection of all measured points. As long as we consider a single 2D projection of the convex polyhedron, then the MABR algorithm (Sect. 3.1) is applied only once.
Fig. 5
The flowchart of the MVBBS method with the MABR algorithm. 
3.3 Data preprocessing
In this paper, we focus on solving the minimum bounding box problem for physical objects that are rectangular objects close to the perfectly shaped bounding box. The measurement points of each side of the objects are given as six sets of points: Front, Back, Right, Left, Top and Bottom. The data set of each side is a n × 3 matrix containing x y and zcoordinates for the n number of points.
In order to reduce the number of points for further computation, the 3D convex hull operation is applied. The input of the convex hull operation are the point coordinates from the six sets of points jointed together as illustrated in Figure 6. The output from the convex hull operation is a matrix with m rows. Each row of the matrix is a convex polyhedron face ϕ _{ i } defined by its vertices. The vertices are given as indices that refer to the input data to the convex hull operation.
Some of the faces of the polyhedron described by will have vertices from two or three sides of the physical object. For example, the measured points from the Top side may be combined with measured points from the Front side into common faces, or “chamfer” faces between the sides. When defining the minimum bounding box in measurement and calibration of rectangular objects, these combined faces and their edges will not contribute to the solution, and they should not be used in the permutation part of the algorithm.
Two data structures are constructed from the output matrix by the preprocessing algorithm. The first structure represents six matrices S ^{ F }, S ^{ B }, S ^{ R }, S ^{ L }, S ^{ T }, S ^{ M } of face vertices v _{ i,j } separated according to the reference object sides (Front, Back,…Bottom) without common faces (Fig. 6, denoted by I); the second is a data matrix P _{ k,4} with x y and zcoordinates for face vertices (Fig. 6, denoted by II).
Fig. 6
The flowchart of the data preprocessing with the output of two data structures I and II. 
3.4 The minimum volume bounding box face (MVBBF) method
The MVBBF method developed by the author is more accurate than the MVBBS method, but it is still an approximation version. The flowchart of the algorithm of MVBBF method is shown in Figure 7.
The theorem presented in Section 2.2 does not provide an upper limit for how many edges that can be coplanar with one side of the bounding box, and then we may assume that one side is coplanar with more than one edge. It is a wellknown fact that two distinct but intersecting lines uniquely determine a plane. Hereby, if a side is coplanar with two edges then it is coplanar with a face of the convex polyhedron. Obviously, one side of the bounding box cannot be coplanar with more than one face of the convex polyhedron. The second adjacent bounding box side must flush with at least one edge or face of the convex polyhedron.
In order to compensate the computation complexity of the MVBBF method, first we apply the data preprocessing (Sect. 3.3). Then, the MVBBF algorithm searches through the six matrices S ^{ F }, S ^{ B }, ...S ^{ M }associated with sides of the measured object and checks all faces within each sample. When a side and the first face ϕ of the polyhedron are chosen, three vertices v _{1,1}, v _{1,2}, v _{1,3} of the face are defined. Two vectors e _{1} {a _{1}, b _{1}, c _{1}} , e _{2} {a _{2}, b _{2}, c _{2}} are constructed based on the three given points P _{1}(x _{1}, y _{1}, z _{1}), P _{2}(x _{2}, y _{2}, z _{2}), P _{3}(x _{3}, y _{3}, z _{3}), Figure 8. The cross product of the two vectors in ℝ ^{3} is a new vector n , which is perpendicular to both given vectors [18], and this vector n is a normal vector to the face ϕ:(3)
Then coordinates of the normal vector n {A, B, C} can be found as the minors of the matrix in (3) as following:(4)
In order to combine the polyhedron face ϕ with an associated bounding box side (e.g. xyplane), we need to align the normal vector n with positive zaxis, Figure 8. The first step is to move the vector n to the origin by using a translation matrix M with the row vector coordinates of the point P _{1}(x _{1}, y _{1}, z _{1}) [19]:(5)
which gives us a vector n _{0}. The projections n _{ α }, n _{ β } of the vector n _{0} on planes yz (x=0) and zx (y=0) respectively (Fig. 8), give us two angles α and β:(6) (7)
Then a rotation matrix R _{ x }(α) with the angle α for rotating counterclockwise around xaxis can be written:(8)
A rotation matrix R _{ y }(β) with the angle β for rotating clockwise around yaxis can be expressed in the following way:(9)
The final transformation matrix T _{ ϕ } to combine the polyhedron face ϕ with xyplane as the bounding box side will be as follows (equivalent to alignment of n with zaxis):(10)
The transformed face ϕ and normal vector n are denoted as ϕ ′ and n ′ in Figure 8. In order to rotate the convex polyhedron, the transformation matrix T _{ ϕ } is applied to the matrix P _{ k,4} (Fig. 6, denoted by II) of the unique polyhedron vertices.
After the coordinate transformation is completed, all newly transformed points are projected into the xyplane. Then the MABR algorithm (Sect. 3.1) is applied for these projected points. It defines an orientation of the “closeloop” of adjacent sides (Sect. 1) and, hence the estimation of width W _{ k } and length L _{ k } of the minimum bounding box. The height H _{ k } is defined as a difference between maximum and minimum zvalues: Z _{max} − Z _{min}. Thus, the volume is: V _{ k } = H _{ k } ⋅ W _{ k } ⋅ L _{ k }.
The described procedure is repeated for each face of the chosen matrix and for all six matrices (S ^{ F }, S ^{ B }, ...S ^{ M }). The minimum volume V _{ k } is calculated in each iteration. After all iterations are completed, the smallest value V _{min} is chosen as the solution.
Fig. 7
The flowchart of the MVBBF method. 
Fig. 8
Coordinate transformation of an arbitrary polyhedron face. 
3.5 the minimum volume bounding box edge (MVBBE) method
The third method corresponds to the conditions of the theorems presented in Section 2.2 and therefore this is the most accurate method, which guarantees the global minimum solution. However, the algorithm is more complex and hence slower than two previous methods. In this case, the data preprocess (Sect. 3.3) becomes the crucial part of the algorithm due to a significant reduction of unnecessary computation of the “chamfer” faces and corresponding edges of the convex polyhedron. The MVBBE algorithm is shown in Figure 9.
The MVBBE method is applied after the 3D convex hull operation and the data preprocess are completed. As before, we use six matrices (S ^{ F }, S ^{ B }, ...S ^{ M }) associated with the cuboid reference object sides as the output of the data preprocessing algorithm (Fig. 6, denoted by I). The algorithm checks for each pair of faces with common edges. Since such pair of two faces with their vertices ϕ _{1} [v _{1,1}, v _{1,2}, v _{1,3}] , ϕ _{2} [v _{2,1}, v _{2,2}, v _{2,3}] are found, it gives us the four noncollinear points P _{0}(x _{0}, y _{0}, z _{0}), P _{1}(x _{1}, y _{1}, z _{1}), P _{2}(x _{2}, y _{2}, z _{2}),P _{3}(x _{3}, y _{3}, z _{3}) and three noncollinear vectors corresponding to the polyhedron edges e _{1} {x _{1} − x _{0}, y _{1} − y _{0}, z _{1} − z _{0}}, e _{2} {x _{2} − x _{0}, y _{2} − y _{0}, z _{2} − z _{0}} and e _{3} {x _{3} − x _{0}, y _{3} − y _{0}, z _{3} − z _{0}} or as a simplified form e _{1} {a _{1}, b _{1}, c _{1}}, e _{2} {a _{2}, b _{2}, c _{2}} and e _{3} {a _{3}, b _{3}, c _{3}} respectively, (Fig. 10).
Thus, the plane corresponding to the face ϕ _{1} can be defined by the two noncollinear vectors e _{2}, e _{1} in the following parametric form:(11)and similarly by e _{1}, e _{3} for the face ϕ _{2}:(12)
The angle θ between the faces ϕ _{1} and ϕ _{2} is the angle between the normal vectors n {A, B, C} , n _{2} {A _{2}, B _{2}, C _{2}} [18]:(13)where A, B, C, A _{2}, B _{2}, C _{2} are three corresponding minors of matrix (11) and (12), which can be calculated by using of equation (4).
In order to find the minimum volume solution, the polyhedron points P _{ k,4} need to be rotated around the common edge e _{1} to the angle θ, from the face ϕ _{1} to the face ϕ _{2}. A onedegree step is used for each iteration, but at least three iterations are applied if the angle θ is less than 2°.
A certain alignment may be done to simplify the rotation of the polyhedron around the edge. First, xyplane is made flush with the face ϕ _{1} by alignment of the normal vector n with zaxis. The same technique is applied as it was described in Section 3.4. The vector n moves to the origin by the translation matrix M(x _{0}, y _{0}, z _{0}) in (5), rotate counterclockwise with angle α around xaxis by using the rotation matrix R _{ x }(α) in (8), and clockwise with angle β around yaxis by using the rotation matrix R _{ y }(β) in (9). The next, the common edge e _{1} is aligned with xaxis by following rotation matrix R _{ z }(γ) around z axis with angle, for clockwise (the example in Figure 10 has positive γcounterclockwise):(14)
Thus, a full transformation matrix T _{ e } for alignment of normal vector n with zaxis and the polyhedron edge e _{1} with xaxis, can be written in this way:(15)
A result of transformation of the two faces ϕ _{1}, ϕ _{2} into ϕ _{1} ′, ϕ _{2} ′ and the edge e _{1} into e ′ _{1} is shown in Figure 10.
The alignments of the face ϕ _{1} ′ with xyplane, and the edge e ′ _{1} with xaxis provide a transformed edge denoted as e ′ _{1} (Fig. 10). Then, the rotation of all points P _{ k,4} around the edge e ′ _{1} with onedegree step angle dθ = π/180° can be proceeded by using the rotation matrix R _{ x }(dθ) given earlier in equation (8). After each rotation step, newly transformed points are projected into xyplane and the MABR algorithm (Sect. 3.1) is applied for the projected points to estimate the width W _{ k } and the length L _{ k } of the minimum bounding box. The height H _{ k } is defined as a difference between maximum and minimum Z _{max} − Z _{min}values. Finally, the volume of the bounding box is: V _{ k } = H _{ k } ⋅ W _{ k } ⋅ L _{ k }.
The above procedure is carried out for each common edge of all six matrices S ^{ F }, S ^{ B }, ...S ^{ M } (Fig. 6, denoted by I). The volume V _{ k } is calculated in each rotation step, and the smallest volume V _{min} is the solution.
Fig. 9
The flowchart of the MVBBE method. 
Fig. 10
Coordinate transformation of two arbitrary polyhedron faces ϕ _{1}, ϕ _{2} with the common edge e _{1.} 
4 Implementation
The algorithms described in the previous sections are developed and implemented in MATLAB^{®} programming environment based on CMM measurement data. The measurements have been performed in a Leitz PMMC600 CMM with an analogue probe. The PCDMIS software was utilized for operation of the CMM.
4.1 Experiment setup
For the experimental tests, we have used a cuboid object with the following nominal dimensions (the true values are unknown): length 210 mm, width 140 mm, and height 120 mm. The test object is shown in Figure 11. The measured data is arranged into separated data samples according to the cuboid sides: Front, Back, Right, Left, Top and Bottom. Each sample is a n × 3 matrix with three columns and nrows of xyzcoordinates corresponding to the nmeasured points as shown in Figure 6. We have used a uniform distribution of measured points with 15 mm distance between the points. The total number of the measured points is N = 650.
In order to get complete measurements of all six sides of the test object in a common coordinate system, we have measured the object in two setups. The measurements of the two setups have been combined by using common alignment points in the two setups.
Fig. 11
CMM measurement of the test object. 
5 Results and discussion
The collected date is further exported to a MATLAB code as an input for the developed algorithms. The first MVBBS method can be applied straightforward on the data − no data preprocess is required. We consider only the Bottom side as a support side. For the other two methods, we apply the data preprocess algorithm after the 3D convex hull operation. The result of the convex hull operation for measured data is shown in Figure 12. There are 166 faces combined together into one convex polyhedron and 88 faces after applying of the data preprocess algorithm (almost 50% of calculations were reduced). The computation results of all three methods are tabulated in Table 2 (the results are rounded to 1e–3).
The MVBBS method provides a significant overestimation of the volume V _{ S } of the bounding box relative to the other two methods: ΔV = V _{ S } − V _{ E } = 951.959 mm^{3}. Meanwhile, there is no difference between estimated volumes from the MVBBF and the MVBBE methods. A possible reason for such coincidence may be a small form deviation and as a result, small angles between polyhedron faces.
An extra test was applied for estimation of MVBB for the cuboid object with the same nominal dimensions but with larger flatness deviations. The computation results are given in Table 3.
The second test demonstrates the difference between MVBBF and MVBBE methods. The following difference can be observed from Table 3: ΔV = V _{ F } − V _{ E } = 8.675 mm^{3}, where V _{ F } is the solution of the MVBBF method and V _{ E } is the solution of the MVBBE method.
In order to verify the proposed approaches, the developed methods were applied on Model B and Model C, which are illustrated in Figure 2b,c. The vertex coordinates of the theoretical models are given in Table 1. The computation results for estimation of MVBB based on the developed methods for Model B and Model C are given in Table 4 (the results are rounded to 1e–4).
It can be observed a difference between the solutions for MVBBS, MVBBF and MVBBE methods for Model C. The MVBBE method provides the smallest solution for Model C. The results for Model B and for all three methods are equal.
The MVBBE method may provide the minimal solution and yet, it includes all solutions of the MVBBF method and therefor it is more reliable and accurate.
Fig. 12
The result of the 3D convex hull operation. 
The computation results of the MVBBS, MVBBF, MVBBE methods for the first test.
The computation results of the MVBBS, MVBBF, MVBBE methods for the second test.
The computation results of the developed methods for Model B and Model C (in normalized units).
6 Conclusion
Three methods have been proposed and demonstrated in this work for estimation of the minimum volume of bounding box with the proposed data preprocess algorithm for the metrological applications. The first two methods are based on a number of assumptions allowing decreasing of a computation time but often with overestimated results. The minimal and the most optimal solution is provided by the MVBBE method. Furthermore, the solution of the MVBBE method is based on theorems presented in this paper (Sects. 2.1 and 2.2) and hence, its estimation is the most accurate. Relying on type of dimensional measurement system, different methods may be applicable while the MVBBE method should utilize as the reference.
However, the MVBBE method includes a large number of an additional calculation. The proposed preprocess data algorithm (Sect. 3.3) based on the specific metrological conditions (described in Sect. 1) allows a significant reduction of the computation (about 50%) preserving the initial accuracy at the same time. Thus, the MVBBE method should be used for those metrological tasks, where the accuracy is the critical factor, particularly when a large geometry form deviation is expected. The principles outlined in this work could also improve the functionality of operation software for the measuring systems.
Acknowledgments
The authors wish to thank Dr. Christoph A. Thieme, NTNU, Trondheim, for valuable advices and comments. The authors acknowledge the financial support of the Research Council of Norway, Grant No. 235315.
References
 N.F. Dupuis, Elements of Synthetic Solid Geometry (Macmillan, 1893) [Google Scholar]
 D. MoulaiKhatir, E. Pairel, H. Favreliere, Int. J. Metrol. Qual. Eng. 9, 15 (2018) [CrossRef] [EDP Sciences] [Google Scholar]
 M. Shamos, Ph.D. thesis, Yale University, 1978 [Google Scholar]
 H. Freeman, R. Shapira, Commun. ACM 18, 409–413 (1975) [CrossRef] [Google Scholar]
 T. Godfried, Solving geometric problems with the rotating calipers, in IEEE MELECON , Greece, 1983 [Google Scholar]
 S. Timos, R. Nick, F. Christos, The R+tree: a dynamic index for multidimensional objects, Figshare (2018) doi:10.1184/R1/6610748.V1 [Google Scholar]
 N. Beckmann, H.P. Kriegel, R. Schneider, B. Seeger, ACM SIGMOD Record 19, 322–331 (1990) [CrossRef] [Google Scholar]
 N. Roussopoulos, D. Leifker, Direct spatial search on pictorial databases using packed Rtrees (1985) doi:10.1145/318898.318900 [Google Scholar]
 S. Gottschalk, M.C. Lin, D. Manocha, OBB tree: a hierarchical structure for rapid interference detection (1996) doi:10.1145/237170.237244 [Google Scholar]
 D. Dimitrov, C. Knauer, K. Kriegel, G. Rote, New upper bounds on the quality of the PCA bounding boxes in r2 and r3 (2007) doi:10.1145/1247069.1247119 [Google Scholar]
 J. O'Rourke, Int. J. Comput. Inf. Sci. 14, 183–199 (1985) [CrossRef] [Google Scholar]
 S. Bespamyatnikh, M. Segal, Inf. Process. Lett. 75, 95–100 (2000) [CrossRef] [Google Scholar]
 M. Lahanas, T. Kemmerer, N. Milickovic, K. Karouzakis, D. Baltas, N. Zamboglou, Med. Phys. 27, 2333–2342 (2020) [CrossRef] [Google Scholar]
 G. Barequet, S. HarPeled, J. Algor. 38, 91–109 (2001) [CrossRef] [Google Scholar]
 D. Dimitrov, M. Holst, C. Knauer, K. Kriegel, Experimental study of bounding box algorithms, in: The Third International Conference on Computer Graphics Theory and Applications , 2008, pp. 15–22 [Google Scholar]
 C. Barber, D. Dobkin, H. Huhdanpaa, ACM Trans. Math. Softw. 22, 469–483 (1996) [CrossRef] [MathSciNet] [Google Scholar]
 F.C. Groen, P.W. Verbeek, N. de Jong, J.W. Klumper, Pattern Recogn. 14, 173–178 (1981) [CrossRef] [Google Scholar]
 P. Aleksandrov, Lectures of Analitical Geometry (Science, Moscow, 1968) [Google Scholar]
 J. Leon Steven, Linear Algebra with Applications, 8th edn. (Pearson, Upper Saddle River, NJ, 2010) [Google Scholar]
Cite this article as: Petr Chelishchev, Knut Sørby, Estimation of Minimum Volume of Bounding Box for Geometrical Metrology, Int. J. Metrol. Qual. Eng. 11, 9 (2020)
All Tables
The computation results of the developed methods for Model B and Model C (in normalized units).
All Figures
Fig. 1
An example of the metrological issue: (a) a cuboid object with CMM measured points; (b) an example of the convex polyhedron with the chamfer faces after convexhull operation; 1–edges; 2–left side; 3–top side; 4–front side; 5–“chamfer” polyhedron faces; 6–ordinary polyhedron faces. 

In the text 
Fig. 2
Examples of convex polyhedrons: (a) a regular tetrahedron with edge length circumscribed by minimal box with edge length 1; (b) convex polyhedron related to Model B; (c) convex polyhedron related to Model C; 1–the edge is flush with the Top side; 2–the edge is flush with the Left side. 

In the text 
Fig. 3
The optimization functions of volume versus orientation angle between two faces (Model C): (a) around the edge 2 on the Left side (small angle); (b) around the edge 1 on the Top side (large angle). 

In the text 
Fig. 4
The MABR of a convex polygon based on 2D point set. 

In the text 
Fig. 5
The flowchart of the MVBBS method with the MABR algorithm. 

In the text 
Fig. 6
The flowchart of the data preprocessing with the output of two data structures I and II. 

In the text 
Fig. 7
The flowchart of the MVBBF method. 

In the text 
Fig. 8
Coordinate transformation of an arbitrary polyhedron face. 

In the text 
Fig. 9
The flowchart of the MVBBE method. 

In the text 
Fig. 10
Coordinate transformation of two arbitrary polyhedron faces ϕ _{1}, ϕ _{2} with the common edge e _{1.} 

In the text 
Fig. 11
CMM measurement of the test object. 

In the text 
Fig. 12
The result of the 3D convex hull operation. 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.