 Open Access
 Total Downloads : 1775
 Authors : V. J. Patel, R. B. Gandhi
 Paper ID : IJERTV1IS4150
 Volume & Issue : Volume 01, Issue 04 (June 2012)
 Published (First Online): 30062012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Evaluation of Circularity from Coordinate data using Maximum Distance Point Strategy (MDPS)
V. J. Patel
Associate Professor, Department of Mechanical Engineering, Birla Vishvakarma Mahavidyalaya (Engineering College), Vallabh Vidyanagar – 388120. Gujarat State, INDIA
R. B. Gandhi
Associate Professor, Department of Mathematics, Birla Vishvakarma Mahavidyalaya (Engineering College), Vallabh Vidyanagar 388120. Gujarat State, INDIA
Abstract
Measurement of cylindrical features using Coordinate Measuring Machine (CMM) is one of the important operations in precision engineering industries. The operation necessitates use of efficient computational algorithms as it has to determine radius/diameter of cylindrical features from measured point coordinates. One of the most widely used algorithm for such application is LeastSquare Method (LSM) which fits a circle to the points measured using CMM. This paper proposes a new approach termed as Maximum Distance Point Strategy (MDPS) to determine radius/diameter of cylindrical feature for minimizing circularity from measured datapoints. The results of MDPS are compared to that of LSM. Moreover, the results of MDPS are also compared with other methods available in literature and it has been found that the results are comparable with the same. It is also demonstrated that the developed methodology offers simplicity in understanding and ease of implementation in computational algorithms.
Keywords: Coordinate Measuring Machine (CMM), LeastSquare Method (LSM), Circularity, Sum of Squared Deviations

Introduction
Many functional components in engineering industries have external or internal cylindrical features. When these components are manufactured, closeness to required dimension is expressed in terms of roundness or circularity. Roundness or circularity can be determined using various instruments such as roundness testing machine, dial gauges, Coordinate Measuring Machines (CMM), gap detectors etc. Among these methods, CMM is widely used in industries due to versatility and ease of operation.
The ANSI Dimensioning and Tolerance Standard Y14.5 [1] defines that the form tolerances on a
component must be evaluated with reference to an ideal geometric feature. CMM software evaluates circularity of cylindrical features by establishing a circle as a reference geometric feature from the measured points using Least Squares Method (LSM). LSM is predominantly used to estimate best fit circle for the measured points. LSM fits geometric feature to minimize the sum of squares of deviations in predefined measures.

Literature Review
Gander, Colub and Trebel [2] used GaussNewton Algorithm (GNA) to minimize the square of error distances for circle. GaussNewton algorithm is a modification of Newtons method, which is linesearch strategy for finding the minimum of a function, mainly used to solve nonlinear least squares problems. If GNA starts nearby the solution, it converges quickly. In other cases, it requires more iteration to converge and sometimes it may not converge at all. Hence, a good initial guess is required for the solution to converge [3].
Shakarji [4] suggested use of LevenbergMarquardt algorithm (LMA) to minimize the square of error distances for various features including circle. LMA is trustregion strategy which provides a numerical solution to the problem of minimizing nonlinear function. LMA is more robust than GNA. However, even for well behaved functions and reasonable starting parameters, the LMA tends to be a bit slower than the GNA. LMA can also be viewed as improved GNA with trust region approach [4, 5, 6]. Also, convergence of the solution is highly dependent on choice of LevenbergMarquardt parameter and its selection is challenging.
Chernov and Ososkov [7] proposed two new set of algorithms for full circlefitting and circular arc namely Iterational Linear Regression Method (ILRM) and Modified Linear Regression Method (MLRM). Although ILRM is wellsuited for fitting any size of circular arc including full circle, it is slower. The second suggested method (MLRM) is faster, but works only for small arcs.
Drezner, Steiner and Wesolowsky [8] suggested use of heuristic algorithms for finding a circle whose circumference is close to given set of points. The heuristic uses two efficient algorithms known as minimax and minisum.
All previous methods are establishing the circle from the measured or simulated points. This circle is base feature for evaluating circularity. Attempts have been also made to develop methods for evaluating error in circularity. Murthy and Abdin [9] applied normal least square fit to determine circularity error but the values obtained are not the minimum for LSM. Instead, they have suggested that simplex search technique is more suitable. To obtain the minimum zone evaluation for sphericity, numerical methods based on the Monte Carlo, Simplex and Spiral Search techniques have also been suggested by Kanada [10]. Murthy [11] compared different algorithms for circularity evaluation and concluded that simplex search is essential and superior to the other methods for evaluating circularity. Shunmugam

suggested an alternative approach based on minimum average deviation (MAD) in which different geometric features are established using a search technique. The values obtained by this approach are compared with the ones obtained using least squares and minimum deviation methods. Dhanish and Shunmugam

determined minimum zone values using discrete and linear Chebyshev approximations which is applied directly to form data as well as coordinate data provided by CMM. An algorithm suggested by Dhanish [14] guarantees the minimum value of circularity error. Kim and Kim [15] proposed an algorithm for least squares evaluation of circularity which takes geometrical approximation of the orthogonal Euclidean distance in measuring deviational errors of sample data over very small arc so that the assessment criterion of normal least squares is faithfully implemented. Wang, Hossein Cheraghi and Masud [16] formulated a nonlinear optimization problem to find circularity error based on the minimum radial separation criterion. Samuel and Shumugam [17, 18] suggested methods based on computational geometric techniques to deal with CMM measured data and form data.
The present work aims to define a strategy that finds best fit circle for given set of data points to minimize circularity and it is named as Maximum Distance Point Strategy (MDPS). For the purpose of comparison, results of MDPS are compared with LSM and CMM results. The results of MDPS are also compared with results of methods published in references [9] and [17].
This is a customized approach to find the best fit circle for evaluating the circularity rather than addressing a general unconstrained nonlinear problem. It is based on the postulate that A unique circle passes through any three noncollinear points in a plane. Hence, selection
of three points (triplet) plays important role to fit the best circle.


Point Selection
The selection procedure for triplet (A, B, C) is as follow.

Let Pi(xi, yi), i = 1,2, , n and n > 2, be the CMM measured set of n points.

Select a point from Pi and name it as A, which is first point in triplet.

Calculate distance from point A to each point Pi
using equation 2.1.
APi = (xa xi)2 (ya yi)2 (3.1)
where, APi is distance from point A to point Pi, i = 1,2, , n,
xa, ya are coordinates of pont A,
xi, yi are coordinates of point Pi.

Select second point from Pi, i = 1,2, , n (second point in triplet) for which APi is maximum. Name it as B.

Point C (third point in triplet) is selected from Pi, i = 1,2, , n such that its normal distance from line AB is maximum.
To determine maximum normal distance, the following expression is used.
d(Pi) = (yB yA) (xi xA) + (xB xA) (yi yA) (3.2)
where, i = 1,2, , n
xa, ya are coordinates of point A, xb, yb are coordinates of point B, xi, yi are coordinates of point Pi.
The selection procedure is repeated for each point Pi, i = 1,2, , n. Hence, there are n triplets and n candidate circles passing through the triplets.
In figure 3.1, selection procedure for point 1 as first point in triplet is shown. Since, distance between point 1 and point 3 is the maximum amongst all points, point 3 is selected as second point in triplet. Point 5 is selected as third point in triplet as its distance from line AB is the maximum. The circle shown in figure 3.1 is candidate circle for point 1.
Amongst all candidate circles, circles which are far from the solution are eliminated heuristically as discussed in section 4.3. The average of center coordinates of the selected circles and the average radii of these circles represent the center and radius of the best fit circle for a given set of points.
2(xb xa)x0 + 2(yb ya)y0 = (x2 x2) + (y2 y2)
b a b a
C
a
C
a
2(xC xa)x0 + 2(yC ya)y0 = (x2 x2) + (y2 y2)
for center of the circle (x0, y0) and calculate r0 using r0 = (xa x0)2 + (ya y0)2. This is the circle passing through (xa, ya), (xb, yb) and (xC, yC).
Repeating the procedure by fixing each point Pi, i =
1, 2, n, ncenters and nradii are found. To select the best fit circle following heuristic method is used.

Let
n
2
ek = I [(xi ak)2 + (yi bk)2 rk]
i=l
Figure 3.1 Selection Procedures for Triplet.

Formulations
For Pi(xi, yi), i = 1,2, , n and n > 2.

Least Square Method
A circle with the center (x0, y0) and radius r0 is found such that it minimizes the sum of squared deviations. The circle equation in an implicit form can be written as
0
f(x, y) = (x x0)2 + (y y0)2 r2 = 0
The deviation of distance for a point Pi, i = 1,2, , n
may be explicitly written as
ei = (xi x0)2 + (yi y0)2 r0; i = 1,2, , n
(4.1)
The sum of squared deviations is then described as
(ak, bk) is center and rk is radius of kth circle where, k = 1,2, n.



The mean and standard deviation of ek, k = 1,2, n are found.

The circles with ek less than or equal to mean of ek, k = 1,2, n are selected.

Calculate the mean of the coordinates of centers and radii of these selected circles. This gives center and radius of the best fit circle.

Calculate circularity using equation (3.3) for the circle found in step 4.

Steps 1 to 5 are followed for (n m) number of circles; where m is number of circles which are not selected in step 3.

If circularity calculated in step 5 is less than circularity calculated in previous iteration, go to step 7. Otherwise go to step 8.

The circle found in second last iteration is the claimed best fit circle.

e = n
e2 = n
[(xx )2 + (y y )2 r ]2
s
(4.2)
i=l i
i=l i 0
i 0 0

Circularity error
Denote the maximum value among the deviations ei, i = 1,2, , n as emax and the minimum value as emin. Then, the circularity error h can be computed as (refer Figure 4.1)
h = emax emin (4.3)
According to the minimum zone criterion given by ANSI Standard Y14.5 [1], the center (x0, y0) and radius r0 of an ideal circle should be determined such that the circularity h is the minimum.

Maximum Distance Point Strategy
Fix a point, say, Pk and select two other points as explained in section 3. Let the coordinates of the points be (xa, ya), (xb, yb) and (xC, yC). Solve the following system of linear algebraic equations
Figure 4.1 Definition of circularity error.

Results and Discussion
MATLAB programs for evaluating circularity by MDPS and LSM were executed on computer with Intel atom processor, 800 MHz clock speed and 1 GB RAM. The programs were run for CMM measured data set. A hole (circular feature) is measured using SCAN facility available on CMM. The SCAN facility ensures that points in the dataset are uniformly spaced. These measured points are tabulated in Table 1.
Table 2 shows results of circularity (h) evaluation for the dataset presented in Table 1. The results of MDPS and LSM are expressed up to six decimal places. It can be observed that circularity error obtained by MDPS is less than that of LSM. It can also be observed that the same is more than that obtained by CMM result. The CMM results were available up to three decimal places. If circle coordinates and radius values obtained by MDPS are rounded to third decimal place, the circularity error is the same as that obtained by CMM. Table 2 also shows the comparison of sum of squared deviation (es). It can be observed that sum of squared deviation of MDPS is minimum amongst all.
Simplex search is superior to the other methods in many cases [11]. Murthy and Abdin [9] have applied simplex search to find a circle to minimize the circularity error on simulated dataset. The same dataset is used to evaluate MDPS. The circularity error obtained by MDPS appears to be more than simplex search, but it is less than that obtained through LSM (refer Table 3). The MDPS can be used as starting solution for simplex search which can reduce number of iterations in finding the circle by simplex search method.
The programs are also executed for the data presented in table 1(a) of Samuel and Shunmugam [17]. Table 4 summarizes the results for circularity evaluation. It can be seen that the MDPS gives less circularity error than that of LSM, MCC (Maximum Circumscribe Circle) and MIC (Minimum Inscribe Circle). The circularity error obtained by MZ (Minimum Zone) is less than that of MDPS, but sum of squared deviation is higher.

Conclusions
The present paper proposes an approach termed as MDPS to determine dimensions of a cylindrical feature from CMM measured point datasets. MDPS is a simple method to understand and to implement amongst similar methods. It gives better results compared to Least Square Method (LSM) for CMM measured points (Table 2). It is also good on evaluating simulated dataset (Table 3). Results of MDPS are comparable with that of Simplex Search method. This method can be used as starting solution for Simplex Search as its solution is closer to Simplex Search compared to LSM. The MDPS results are also showing its potential compared to Maximum Circumscribe Circle (MCC), Minimum Inscribe Circle
(MIC) and Minimum Zone (MZ) (Table 4). The developed methodology has great potential for implementation in CMM software for evaluation of circular features.

References

ANSI Standard Y14.5, Dimensioning and Tolerancing, The American Society of Mechanical Engineers, New York, 2009.

Gander, Colub and Strebel, LeastSquares Fitting of Circles and Ellipses, BIT Numerical Mathematics, Vol. 34 No. 4, pp 558578, 1994. doi: 10.1007/BF01934268

Ravindran, K. M. Radsgell and G. V. Reklaitis Engineering Optimization: Methods and Application, Second Edition, John Wiley & Sons, 2006.

Shakarji, LeastSquares Fitting Algorithms of the NIST Algorithm Testing System, Journal of Research of the National Institute of Standards and Technology, vol. 103 no. 6, pp 633641, 1998.

Nocdal and Wright, Numerical Optimization, Springer Verlag, New York, 1999.

Antoniou and Lu, Practical Optimization: Algorithms and Engineering Applications, Springer Science+Business Media, 2007.

Chernov and Ososkov, Effective Algorithms for Circle Fitting, Computer Physics Communications, vol. 33 no. 4, pp 329333, 1984 doi:10.1016/00104655(84)901371

Drezner, Steiner and Wesolowsky, On the Circle Closest to Set of Points, Computer and Operations Research, vol. 29 no. 6, pp 637650, 2002. doi:10.1016/S0305 0548(99)001057

Murthy and Abdin, Minimum Zone Evaluation of Surfaces, International Journal of Machine Tool Design and Research, vol. 20 no. 2, pp. 123136, 1980 doi:10.1016/00207357(80)900244

Kanada, Evaluation of spherical form errorscomputation of sphericity by means of minimum zone method and some examinations with using simulated data, Precision Engineering, vol. 17 no. 4, pp 281289, 1995. doi:10.1016/01416359(95)000178

Murthy, A Comparison of Different Algorithm for Circularity Evaluation, Precision Engineering, vol 8 no. 1, pp 1923, 1986 doi:10.1016/01416359(86)90005X

Shunmugam, New approach for evaluating form errors of engineering surfaces, Computer Aided Design, vol. 19 no. 7, pp 368374, 1987 doi:10.1016/00104485(87)900376

Dhanish and Shunmugam, An algorithm for form error evaluation using the theory of discrete and linear Chebyshev approximations, Computer Methods in Applied Mechanics and Engineering, vol. 92 no. 3, pp 309324, 1991. doi:10.1016/00457825(91)900193

Dhanish, A simple algorithm for evaluation of minimum zone circularity error from coordinate data, International Journal of Machine Tools & Manufacture, vol. 42 no. 14, pp 15891594, 2002. doi:10.1016/S08906955(02)001360

Kim and Kim, Geometrical tolerances: improved linear approximation of least squares evaluation of circularity by minimum variance, International Journal of Machine
Tools & Manufacture, vol. 36 no. 3, pp 355366, 1996. doi:10.1016/08906955(95)000569

Wang, Hossein Cheraghi and Masud, Circularity error evaluation theory and algorithm, Precision Engineering, vol. 23 no. 3, pp 164176, 1999. doi:10.1016/S0141 6359(99)000069

Samuel and Shunmugam, Evaluation of circularity from coordinate and form data using computational geometric
techniques, Precision Engineering, vol. 24 no. 3, pp 251
263, 2000. doi:10.1016/S01416359(00)000398

Samuel and Shunmugam, Evaluation of circularity and sphericity from coordinate measurement data, Journal of Materials Processing Technology, vol. 139 no. 13, 9095, 2003. doi:10.1016/S09240136(03)001870
Table 1: CMM measured dataset.
I 
xi 
yi 
i 
xi 
yi 
i 
xi 
yi 
1 
182.096 
115.902 
26 
227.545 
89.313 
51 
228.262 
141.939 
2 
182.197 
113.365 
27 
229.708 
90.658 
52 
226.034 
143.155 
3 
182.508 
110.845 
28 
231.741 
92.17 
53 
223.724 
144.178 
4 
183.027 
108.362 
29 
233.655 
93.859 
54 
221.329 
145.008 
5 
183.753 
105.926 
30 
235.412 
95.693 
55 
218.869 
145.637 
6 
184.682 
103.554 
31 
237.017 
97.675 
56 
216.369 
146.059 
7 
185.799 
101.28 
32 
238.45 
99.784 
57 
213.842 
146.271 
8 
187.102 
99.105 
33 
239.699 
102 
58 
211.318 
146.272 
9 
188.589 
97.035 
34 
240.757 
104.309 
59 
208.793 
146.064 
10 
190.236 
95.106 
35 
241.621 
106.703 
60 
206.293 
145.646 
11 
192.045 
93.315 
36 
242.281 
109.159 
61 
203.833 
145.021 
12 
193.99 
91.686 
37 
242.735 
111.665 
62 
201.433 
144.193 
13 
196.067 
90.223 
38 
242.977 
114.193 
63 
199.118 
143.172 
14 
198.262 
88.935 
39 
243.009 
116.714 
64 
196.892 
141.96 
15 
200.563 
87.834 
40 
242.83 
119.249 
65 
194.777 
140.569 
16 
202.941 
86.93 
41 
242.44 
121.762 
66 
192.784 
139.006 
17 
205.384 
86.229 
42 
241.842 
124.229 
67 
190.925 
137.281 
18 
207.878 
85.734 
43 
241.043 
126.635 
68 
189.214 
135.406 
19 
210.409 
85.448 
44 
240.045 
128.968 
69 
187.67 
133.4 
20 
212.951 
85.375 
45 
238.854 
131.216 
70 
186.292 
131.263 
21 
215.492 
85.514 
46 
237.485 
133.347 
71 
185.1 
129.026 
22 
218.012 
85.864 
47 
235.933 
135.37 
72 
184.097 
126.693 
23 
220.492 
86.423 
48 
234.232 
137.242 
73 
183.292 
124.287 
24 
222.925 
87.19 
49 
232.38 
138.967 
74 
182.691 
121.823 
25 
225.272 
88.152 
50 
230.383 
140.539 
75 
182.295 
119.313 
Table 2: Results of circularity evaluation for measured points tabulated in Appendix A.
x0 (mm) 
y0 (mm) 
r0 (mm) 
h (Âµm) 
Sum of squared deviation, es 

MDPS 
212.559041 
115.834956 
30.462729 
1.151146 
6.2964Ã—10006 
LSM 
212.559001 
115.834943 
30.462731 
1.170239 
1.6659Ã—10005 
CMM result 
212.559 
115.835 
30.463 
1.125702 
1.1785Ã—10005 
MDPS Maximum Distance Point Strategy, LSM Least Square Method
Table 3: Results of circularity evaluation for data presented in Muthy and Abdin [9].
x0 (mm) 
y0 (mm) 
r0 (mm) 
h (Âµm) 
Sum of squared deviation, es 

MDPS 
2.363043 
0.526847 
16.165762 
0.972108 
1.830282 
LSM 
2.088 
1.206 
16.027 
1.829877 
5.689571 
Simplex 
2.1268 
1.1095 
– * 
0.955 
– * 
*R(Radius) is not presented in the reference, hence Sum of squared deviation cannot be calculated
Table 4: Results of circularity evaluation for data presented in Samuel and Shunmugham [17].
x0 (mm) 
y0 (mm) 
r0 (mm) 
h (Âµm) 
Sum of squared deviation, es 

MDPS 
39.999741 
30.002065 
25.003333 
2.3737 
7.5750Ã—10006 
LSM 
40.0002 
30.0012 
25.0030 
4.0930 
1.1302Ã—10005 
MCC 
40.0000 
30.0014 
25.0040 
3.6102 
1.7539Ã—10005 
MIC 
40.0000 
30.0010 
25.0020 
4.2930 
1.7539Ã—10005 
MZ 
39.9998 
30.0022 
25.0030 
2.2621 
6.3538Ã—10005 
MCC Maximum Circumscribe Circle, MIC Minimum Inscribe Circle, MZ Minimum Zone