JIANG Li(姜黎)， ZHANG Zhi-jing(張之敬)， WU Wei-ren(吳偉仁)，，JIN Xin(金鑫)， JIE De-gang(節(jié)德剛)

(1.School of Mechanical and Vehicular Engineering，Beijing Institute of Technology，Beijing 100081，China;2.Lunar Exploration and Aerospace Engineering Center，Beijing 100037，China)

Micro parts are widely used in aerospace，micro-electro-mechanical systems(MEMS)and other fields.The technology development establishes stricter standards for functionalities，performances and reliability ofthe micro parts.Therefore，the precision detection technologies for micro parts with geometric parameters within the range of 0.01－10 mm have attracted more researchers’attentions throughout the world.Because the microscope method assisted with precise displacement of mechanical platform possesses higher inspection efficiency than other inspection method，e.g.universal tool measuring microscope and coordinate measurement machine，it has been widely used in precision measurement of micro parts［1］.

Since micro-edges of the micro part are complex，measurements of different data fitting methods are distinguished for the same geometric parameter［2－3］.This exerts significantly negative influences on the quality judgment for micro parts.For the roundness error evaluation，the minimum zone circle(MZC)method meets the minimum condition and can be used to obtain the minimum evaluation result which is the minimum radius difference between two concentric circles that enclose all data points.And therefore，the MZC method has caught the researchers’attention［4－5］.Up to date，scholars throughout the world have conducted a substantial number of researches on the MZC method and proposed many optimization algorithms［6－9］.For evaluating the roundness error，these algorithms have to do a great amount of computations.This limitation makes these algorithms inapplicable to the practical engineering measurement.In recent years，for reducing computation complexity the convex hull theory has been applied to evaluating form errors［10－11］.In this paper，the convex hull will be used to develop an improved algorithm of MZC(IMZC)for evaluating the roundness errors of micro parts.

1 Evaluation of roundness error via MZC

For discrete measurement，the roundness error is defined as the minimum radial separation between two concentric circles that enclose all data points from the circle contour［12］.For evaluating roundness errors，there are four common methods，i.e.least square circle(LSC)，minimum circumscribed circle(MCC)，maximum inscribed circle(MIC)and MZC.According to the definition，MZC yields the smallest zone than other methods，and thus obtains the minimum radial separation between two circles which enclose all points of the profile［13］，as shown in Fig.1.

Fig.1 Concentric circles of minimum zone

The MZC roundness error evaluation takes the“2+2”model.It means that the four tangent points are used to construct two concentric circles，i.e.the maximum and the minimum circles which all data points lie on or inside and whose radius distance takes the minimum value.The MZC roundness error，fMZC，is measured with the minimum radius distance，rmax－ rmin，where rmaxis the radius of the maximum circle and rminis the radius of the minimum circle.The distribution of the four tangent points takes two forms，the highlow-high-low and low-high-low-high，as shown in Fig.2.

Fig.2 Model of MZC

Therefore，an important step for evaluating roundness errors of micro parts is to find the two concentric circleswhich enclose allsampling points of the contour.According to the above analysis，the key to the step is to find four tangent points，two on the maximum circle and the other two on the minimum circle.

2 Improved algorithm of MZC via convex hull

According to the above analysis，the key to the roundness error evaluation via MZC is to determine two concentric circles with the minimum radius difference which enclose allsampling points of the contour.According to the criteria for the two circles，two tangent points on the maximum circle are on the circumscribed convex polygon of the sampling points.Thus，once the circumscribed convex polygon is determined，it is easy to find these two tangent points.The determination of the circumscribed convex polygon can be done with a convex hull algorithm.After processing the sampling points p of the contour，two point sets，pMCCand pMIC，will be available，where pMCCis a convex set for finding two tangent points on the maximum circle and pMICis a non-convex set for finding the other two tangent points on the minimum circle.Based on these four tangent points，the roundness error evaluation via MZC can be done easily.

2.1 Processing the contour points via convex hull

The convex hull definition:

Given a set S={s1，s2，…，sN}of points in the plane，the convex hull conv(S)is the smallest convex polygon in the plane that encloses all points in the set S［14］.The key to determining the convex hull for the set S is to find some points which construct the convex hull.These points are called the convex points.

Procedures for finding the vertexes of the convex hull are as follows:

Step 1Sorting the contour points

For a given set of data points Q，let c be the point in Q with the minimum y-coordinate，or the leftmost such point in case of a tie.The remaining points in Q are sorted in the counterclockwise order by polar angles between the x-axis and the vector linking the points c and qito construct a new point set P={pi|pi=(xi，yi)，i=1，2，…，n}，wherein xi，yiare the coordinates of the point pi.

Step 2Judgment of the vertexes of the convex hull

Let c be an index to the newly found convex point.According to the first step，the first point in P is a convex point.Thus，at the beginning，c is equal to 1.For the ithpoint piin the point set P(1 ＜ i ＜ n)，calculate the value of s(pc，pi，pi+1)as

If s(pc，pi，pi+1)is larger than 0，piis a convex point and let c take the value of i.Otherwise，piis not a convex point and remove this point from the point set P.If i is equal to n－1，all points in P are convex points.Otherwise，add 1 to i and according to the above process check whether this new ithpoint piis a convex point.This calculation and check process will be completed for every point in the point set P(1＜i＜n).

According to the above procedure，many algorithms have been developed since the 70’s of the last century.The typical algorithms included Graham Scan，Gift Wrapping，the“divide-andconquer”algorithm and so on［15］.Since the computational complexity of Graham Scan achieves the lower limit O(nlog n)［16］，Graham Scan algorithm is adopted for the roundness error evaluation to sort the contour points into two point sets，pMCCand pMIC，where pMCCis the set of circumscribed circle points and pMICis the set of inscribed circle points.Flow chart of this algorithm is shown in Fig.3.

Fig.3 Contour point processing flow chart

2.2 Determination of four tangent points

There are two steps to find the four tangent points from these two data point sets of pMCCand pMIC.The first step is to determine two or three vertexes on the minimum circumscribed circle and to store these vertexes in a point set VMCC.Determining two or three vertexes on the maximum inscribed circle is also included in the first step.These vertexes on the maximum inscribed circle are stored in another point set of VMIC.It must be noted that the sizes of these two sets，VMCCand VMIC，cannot contain two points as the same time.The detailed information about how to determine vertexes from pMCCand pMICare discussed by Jywe W.et al［17］.Based on the relationship between the MZC，the maximum inscribed circle and the MZC［17－18］，the second step is to find the four tangent points，two from VMICand two from VMCC.The procedure for determining these four tangent points is illustrated in Fig.4.

Fig.4 Four tangent points determination algorithm

2.3 Calculation of roundness error

Using the four determined tangent points，the center of the minimum zone reference circles is found as shown in Fig.5.In Fig.5，L1is a straight line through tangent points of b and d on the outer minimum zone reference circle and L2is a straight line through tangent points of a and c on the inner minimum zone reference circle.L3and L4are perpendicular lines to L1and L2，respectively.These two perpendicular lines have slopes of k1and k2.Calculate the reference circle center，(cx，cy)，as follows:

where(xm1，ym1)is the middle point between b and d，and(xm2，ym2)the middle between a and c.

Fig.5 Four tangent points of MZC

After determining the reference circle center，the radius，rmax，of the outer minimum zone reference circle is equal to the distance between the center and b or d，and the radius，rmin，of the inner minimum zone reference circle is the distance between the center and a or c.At this stage，the roundness error，fMZC，via MZC is evaluated as the difference between rmaxand rmin

3 Performance analysis

To verify the accuracy and efficiency of the IMZC，in this section，measurements of a cylindrical part produced by the turning operation and the center hole of two fine-pitch gears is used.The roundness error evaluation results via IMZC，MZC and LSC is analyzed.

3.1 Evaluation result analysis for cylindrical part by turning operation

The contour of the turning cylindrical part with the radius of 15 mm is measured with Mitutoyo Roundness Measuring Equipment RA-2100.Due to the extremely large volume of measured contour points，the original measurements are sampled according to the uniform distribution rules.The sample size is 40.The sampled contour points are listed in Tab.1.Using these sample points，the roundness error for this turning cylindrical part is assessed with LSC，IMZC and the traditional MZC.The assessment results via LSC and IMZC are listed in Tab.2，and the results via MZC and traditional MZC in Tab.3.

Tab.2 shows that the roundness error via LSC is 0.027 0 mm，whereas the roundness error via IMZC 0.0251 mm.From the set of data，IMZC has higher precision than LSC.

Tab.1 Sample contour points mm

Tab.2 Evaluation result via LSC and IMZC mm

Tab.3 Evaluation result via IMZC and MZC

From Tab.3，we can see that IMZC has the same evaluation results with the traditional MZC.The computation time for IMZC by incorporating Graham’s scan convex hull algorithm is less than 10%of the traditional MZC and thus the roundness error evaluation has obtained about 10 efficiency gains.

3.2 Evaluation result analysis for the hole center of fine-pitch gears

Images of these two fine-pitch gears were obtained with a micro-vision inspection and an inspection software code by the authors as shown in Fig.6.The contour points of these two gears were measured via an edge detection algorithm，which is implemented and incorporated into the inspection software.These contour point measurements are evaluated and the roundness error evaluation results are list in Tab.4.These figures in Tab.4 verify the practicability and reliability of IMZC.

Fig.6 Image of fine-pitch gear

Tab.4 Evaluation result of roundness error evaluation for two fine-pitch gears mm

4 Conclusion

In this paper，using the convex hull algorithm，an improved algorithm of MZC(IMZC)method was developed for evaluating roundness errors of micro parts.IMZC is simple and can be implemented easilyviacomputer programming languages.It can assess roundness errors according to contour point measurements in rectangular and polar coordinate system.The performance of IMZC was analyzed according to contour point measurements of a cylindrical part produced by the turning operation and the center hole of finepitch gears.The analysis results showed that IMZC had the same precision with the traditional MZC and higher precision than least squares circle(LSC).The results showed that the computation time of IMZC is just 6.89%of traditional MZC，demonstrating the high efficiency of the IMZC.

［1］ Wang Xiangjun，Wang Feng.Study of micro mechanical size inspection technology by microscope precision digital image［J］.Optics and Precision Engineering，2001，19(6):511－513.(in Chinese)

［2］ Zhang Zhijing，Du Fang，Jin Xin，et al.Complex edge recognition algotithm of micro-accessory［J］.Optics and Precision Engineering，2009，17(2):355－361.(in Chinese)

［3］ Zhang Lin，Zhang Zhijing，Jin Xin，et al.Study on measuring algorithms of geometry in microscope inspection method［J］.Tool Engineering，2009，43(10):88－91.(in Chinese)

［4］ Zheng Xiang，Ruan Zhiqiang，Xia Weiming.Minimum circum scribed circle finite element post-processing algorithm for coaxial error［J］.Journal of Southeast University，2009，39(6):1156－1160.(in Chinese)

［5］ Liu Fei，Liang Lin，Peng Xiaonan.Evaluating and application algorithm of minimum zone circle for roundness error in cartesian coordinate system［J］.Tool Engineering，2011，45(5):87 －90.(in Chinese)

［6］ Zhang Tieying，Lai Kewei.Study on computational geometry approaches to assessing roundnes［J］.Journal of Engineering Graphics，2002(3):145 －153.(in Chinese)

［7］ Yue Wuling，Wu Yong.Roundness error based on quasi-incremental algorithm［J］.Chinese Journal of Mechanical Engineering，2008，44(1):87－91.(in Chinese)

［8］ Cui Changcai，Che Rensheng，Ye Dong.Circularity error evaluation using genetic algorithm［J］.Optics and Precision Engineering，2001，9(6):499 － 505.(in Chinese)

［9］ Andrea R，Matteo A，Barloscio Matteo B，et al.Fast genetic algorithm for roundness evaluation by the minimum zone tolerance(MZT)method［J］.Measurement，2011，44(7):1243 －1252.

［10］ Lee M K.An enhanced convex-hull edge method for flatness tolerance evaluation［J］.Computer-Aided design，2009，41(12):930 －941.

［11］ Li Xiuming，Shi Zhaoyao.Development and application of convex hull in the assessment of roundness error［J］.Machine Tools and Manufacture，2008，48(1):135－139.

［12］ He Yongxin，Wu Chongpei.Geometry presion criterion［M］.Beijing:Beijing Institute of Technology Press，2003:35－37.(in Chinese)

［13］ Ni Xiaohua.Evaluation of form error and measurement uncertainty［M］.Beijing:Chemical Industry Press，2008:20－45.(in Chinese)

［14］ Zhou Wenke.An accelerating algorithm for computing convex hull of simple polygon［J］.Journal of Guangzhou University:Natural Science Edition，2003，2(6):546－547.(in Chinese)

［15］ de Berg M，van Kreveld M.Computional geometry:algorithm and applications［M］.Beijing:Tsinghua University Press，2009:3 －10.

［16］ Yao A C.A lower bound to finding convex hulls［J］.Journal of the ACM，1981，28(4):780－787.

［17］ Jywe Wenyuh，Liu Chienhong，Chen Cha'okuang.The min-max problem for evaluating the form error of a circle［J］.Measurement，1999，26(4):273 －282.

［18］ Li Xiuming，Shi Zhaoyao.The relationship between the minimum zone circle and the maximum inscribed circle and the minimum circumscribed circle［J］.Precision Engineering，2009，33(3):284－290.