# Primitive Shape Fitting in Point Clouds Using the Bees Algorithm
## 3 Primitive Fitting Methods
### Fitness Function  
The term 'fitness function' is adopted from the EA terminology, and is widely used in the wider metaheuristics literature. In the proposed application, the fitness function quantifies the goodness of fit of a primitive shape \(I\) to a given point cloud \(\mathcal{PC}=\{p_{1},\ldots,p_{N}\}\) of \(N\) elements. The evaluation criterion for the goodness of fit takes into account two factors: the distance \(\delta(p_{i},I)\) between each of the individual points \(p_{i}\in\mathcal{PC}\) and the surface of the primitive \(I\); and the concordance \(NC(p_{i},I)\) of the normals, calculated at each point \(p_{i}\in\mathcal{PC}\), and its projection \(\pi(p_{i},I)\) on the closest surface of the primitive:  
\[\mathcal{F}(I,\mathcal{PC})=\frac{1}{N}\sum_{i=1}^{N}\frac{NC(p_{i},I)}{1+ \frac{\delta(p_{i},I)}{\delta_{max}}^{2}} \tag{1}\]  
where the normalisation factor \(\delta_{max}\) is the distance between the centroid and the outmost element of the PC. Given a point \(p_{i}\in\mathcal{PC}\), the projection \(\pi(p_{i},I)\) is the closest part of the candidate primitive surface to the point \(p_{i}\). The computation of \(\pi(p_{i},I)\) is easy for primitive shapes, and it can be computed very efficiently. The calculation of \(NC(p_{i},I)\) necessitates of a method to calculate the normals to the elements of a PC. If the normals are not known, the reader is referred to the literature [27; 28] for a suitable extraction method. The function in Equation (1) is the same for each type of primitive, whilst the concordance of normals \(NC(p_{i},I)\) and distance \(\delta(p_{i},I)\) are type-specific.  
For a given sphere \(S\), the distance \(\delta(p_{i},S)\) between an arbitrary point \(p_{i}\) and \(I=S\) is computed as:  
\[\delta(p_{i},S)=|d(p_{i},S_{c})-S_{r}| \tag{2}\]  
where the function \(d(A,B)\) measures the Euclidean distance between points \(A\) and \(B\), and \(S_{c}\) and \(S_{r}\) are respectively the centre and radius of \(S\). For the box and cylinder, \(\delta(p_{i},I)\) is computed as the distance between point \(p_{i}\in\mathcal{PC}\) and its projection \(\pi(p_{i},I)\):  
\[\delta(p_{i},I)=|d(p_{i},\pi(p_{i},I))| \tag{3}\]  
The concordance of normals \(NC(p_{i},I)\) is computed using the cosine similarity between the normal \(N(p_{i})\) to point \(p_{i}\in\mathcal{PC}\) and the normal \(N(\pi(p_{i},I))\) of its projection on the candidate primitive surface:  
\[NC(p_{i},I)=\max\left(\frac{N(p_{i})\cdot N(\pi(p_{i},I))}{\|N(p_{i})\|\,\|N( \pi(p_{i},I))\|},0\right) \tag{4}\]  
where \(\cdot\) denotes the dot product between two vectors. Using Equation (4), only normals that agree in direction contribute to the calculation of the goodness of fit.  
From Equation (1), it is easy to see that \(\frac{\delta(p_{i},l)}{\delta_{max}}^{2}\) is minimum and equal to zero when the shape fits perfectly the data. In this case, the denominator of Equation (1) is minimum and equal to 1. The numerator is maximum and equal to 1 when the shape fits perfectly the data, and all the normals agree. Hence, the parameter fitting problem consists of maximising the output of \(\mathcal{F}(I,\mathcal{PC})\).