# Primitive Shape Fitting in Point Clouds Using the Bees Algorithm
## 3 Primitive Fitting Methods
### Ransac  
As seen in Section 2, a number of RANSAC implementations were proposed in the literature. The main variations over the standard procedure concerned the use of heuristics for faster execution, rather than changes in the search procedure. Often, the precise algorithmic details of these RANSAC variants were not fully reported, and for this reason the standard procedure was implemented in this study [5]. RANSAC is an iterative process, where one new candidate shape is created and scored every cycle. Each iteration comprises of three primary subroutines.  
The first RANSAC subroutine creates a minimal subset \(P_{ms}\) of points, where \(P_{ms}\subset\mathcal{PC}=\{p_{1},\ldots,p_{N}\}\) and \(ms<N\). The subset \(P_{ms}\) contains the minimum number of points needed to fully define a candidate shape. Namely, four points are needed to define a sphere, five to define a cylinder and six to define a box (Figure 2).  
Figure 2: Four non coplanar points are used to define a sphere (see **left**). Five points are used to define a cylinder, with one on each end face and three on the outer cylindrical surface (see **top right**). Six points are used to define a box, one point for each side (see **bottom right**). Note that the cylinder and box require estimated surface normals to the PC to validate the minimal set of points.  
For the sphere, all four points are randomly sampled at once, and resampled if they are coplanar. For the cylinder and box, one point is picked from the PC at a time, and a set of tests are performed to determine if the newly sampled point is on the same or a different shape face to the points already populating \(P_{ms}\) (i.e., all normals must be perpendicular or of opposite direction to each other). The newly sampled point is added if it lies on a different face respect to all points in \(P_{ms}\), otherwise is discarded. In the case of the box, the goal of the sampling procedure is to have a point on every face. In the case of the cylinder, the goal is to have three points on the cylindrical outer surface, and one point on each of the end faces.  
The second RANSAC subroutine defines a candidate primitive shape from \(P_{ms}\). The parameters required to fully define a shape are similar to those defined in Section 3.1, with the sole difference of the use of Euler's angles (i.e., roll, pitch, yaw) instead of quaternions to define orientation. For spherical primitives, the parameters were found using [PERSON]'s technique [PERSON] (1966). For cylinders and boxes, the orientation of the shape is found using the normals to two of the points in \(P_{ms}\) (once the orientation of two perpendicular faces is found, the third dimension can be retrieved from the right-hand rule). After the orientation of the candidate shape is found, the size is determined from the whole set of points in \(P_{ms}\) (pairs of points in \(P_{ms}\) on opposite faces delimit the boundaries of the candidate shape). Finally, the centre is calculated from the reconstructed shape.  
The third and final step is to score the candidate primitive shape. The score is calculated as follows:  
\[Score(I)=\sum_{i=1}^{N}\min\{dist(p_{i},I),\epsilon\} \tag{7}\]  
where \(N\) is the number of points in the PC, \(\delta(p_{i},I)\) is the shortest distance between \(p_{i}\) and the surface of the candidate shape \(I\), and \(\epsilon\) is the approximation tolerance. In the RANSAC implementation used in this paper \(\epsilon=0.3\). A perfectly fitting shape scores zero.