uation of data using computational geometric2007

1、International Journal of Machine Tools & Manufacture 47 (2007) 12291236/locate/ijmactoolEvaluation of form data using computational geometric techniquesPart I: Circularity errorN. Venkaiah, M.S. ShunmugamManufacturing Engineering Section, Department of Mechanical Engineering, Indian

2、Institute of Technology Madras, Chennai600036, IndiaReceived 12 March 2006; received in revised form 12 August 2006; accepted 15 August 2006Available online 2 October 2006AbstractThe present work deals with evaluation of form error from the measured proles obtained using a form tester, namely roundn

3、ess/ cylindricity measuring instrument. In Part I, details of circularity evaluation are presented. Due to eccentricity in component setting and radius-suppression inherent in the measurement, circularity error has to be evaluated with reference to a limacon. A computational geometry-based algorithm

4、 is proposed for establishing minimum circumscribed, maximum inscribed and minimum zone limacons. A new type of control hull for directly constructing equi-angular diagrams and a new procedure for updating are introduced. Validation has been done with bench-mark data set and corresponding results av

5、ailable in the literature. Being geometry-based algorithm, it is simple to follow and each iteration can be visualized and interpreted geometrically. On comparison with simplex search method, the proposed algorithm is found to be computationally efcient in terms of accuracy and time taken. The propo

6、sed methods can be easily implemented in computer-aided roundness measuring instruments. Extension of this work for evaluation of cylindricity error has been dealt in Part II. r 2006 Elsevier Ltd. All rights reserved.Keywords: Circularity error; Form data; Limacon; Computational geometry; Control hu

7、ll; Equi-angular diagrams1. Introductionas form data. The form data is usually characterized by equi-spacing.The prole deviations obtained using roundness measur- ing instrument are magnied and plotted on a polar chart. The earlier manufacturers of the instruments provided templates with concentric

8、circles to evaluate the circularity error. Whitehouse 1 and Chetwynd 2, however, showed that due to eccentricity between the rotational center of the instrument and center of the component, even a truly circular component results in a non-circular prole. Evaluation using a pair of concentric circles

9、 would show certain circularity error and an error value greater than the specied tolerance might lead to the rejection of the component. An exact mathematical representation of the measured prole obtained for a truly circular component for a given eccentricity, radius suppression and magnica- tion

10、was obtained and the rst-order approximation was shown to be a limacon 3. Therefore, limacon would be the appropriate assessment feature for evaluation of circularity error. Geometrically, a limacon is obtained as a locus of the foot of the perpendiculars drawn from the origin (pole) to the tangents

11、 of a circle having its center offset from theThe geometric form of any manufactured feature always deviates from its nominal design to some degree, owing to the random and/or systematic errors. In order to satisfy certain functional requirements or assembly conditions, geometric tolerances are usua

12、lly assigned to selected features. One such feature often used in engineering components is a cylindrical feature. In certain applications, it is enough to consider a transverse section of the cylinder and apply circularity tolerance. Verication of this tolerance is done using a roundness tester, wh

13、ich measures the deviations from an ideal circular trajectory established by the instrument. In case of cylindricity measurement, an additional straight datum is used and the measurements are carried out at few transverse sections of the cylinder. In such measurements, the size/radius of the compone

14、nt is always suppressed and the measurement data is referred toCorresponding author. Tel.: +914422574677; fax: +914422570509.E-mail address: shuniitm.ac.in (M.S. Shunmugam).0890-6955/$- see front matter r 2006 Elsevier Ltd. All rights reserved. doi:10.1016/j.ijmachtools.2006.08.0101230N. Venkaiah, M

15、.S. Shunmugam / International Journal of Machine Tools & Manufacture 47 (2007) 12291236origin. Though the templates with concentric circles are no longer provided with roundness testers, the terms such as least squares circle (LSC), maximum inscribed circle (MIC), minimum circumscribed circle (MCC)

16、and mini- mum zone circle (MZC) are quite liberally used by the industry while specifying the method used for evaluating the circularity error.ISO species that an ideal feature must be established from the measured prole such that deviation between it and the measured prole is the least possible val

17、ue 4. In practice, the ideal feature is taken to be a straight line for straightness, a plane for atness, etc. Some researchers simply extend this to circularity evaluation without any consideration to the method of measurement and use a circle as an assessment feature for the form data. Even the us

18、e of the circle is justied with a claim that the limacon is an approximation of a circle and therefore only the circle must be used for obtaining correct results. In some cases, even though the center coordinates of circle for establishing the limacon are obtained using least squares method (LSM), t

19、wo concentric circles are drawn from this center enclosing the entire measured prole and circularity error is evaluated as radial separation between the two circles. The fact that the limacon is the basis for the LSM and the parameters evaluated actually correspond to the limacon is often ignored 5.

20、A number of attempts have been made in the past to evaluate circularity error from the form data obtained using roundness measuring instruments with limacon as the assessment feature. LSM is one such attempt based on a sound mathematical principle that minimizes the sum of the squared deviations of

21、the measured points from the tted limacon feature 6,7. This method is robust, but it does not follow the standards intently and will not guarantee the minimum zone (MZ) solution specied in the standards. The deviation values and the form error that are determined by LSM will be generally larger than

22、 the actual ones, and this may lead to rejection of good parts. To obtain the MZ solution in circularity evaluation, the numerical methods based on simplex linear programming8 and simplex search 9 have been adopted. Shunmugam6 suggested a new simple approach called the median technique, which gives

23、minimum value of circularity error.Using discrete Chebyshev approximations, Danish and Shunmugam 10 have arrived at the MZ values.In the past decade, computational geometric techniques have gained enormous attention from the designers of algorithms for solving geometric problems 11,12. These techniq

24、ues also show greater promise for solving the MZ problems encountered in the geometrical evaluations. They can be very well applied for the evaluation of the circularity error in the manufactured components. Though application of Voronoi diagrams for construction of circle has been reported in the l

25、iterature, rst attempt to develop computa- tional geometric techniques based on limacon was reported by Samuel and Shunmugam 13. Two limacons obtained from the same center, enclosing the entire measured prole and having minimum separation, result in an MZ value. The concepts of function-oriented eva

26、luation, namely methods based on minimum circumscribed (MC) and maximum inscribed (MI) limacons, are also applied for circularity evaluation. In order to obtain MC and MI limacons, convex outer and inner hulls have been used in the past. Construction of convex hulls considerably reduces the number o

27、f candidate points for establishing the assessment limacons. However, there is a need to reduce the candidate points further in cases where a large number of data points are to be evaluated. It is also observed that the algorithms used to construct the convex inner hull are not quite consistent 5,13

28、.Part I deals with the evaluation of circularity errorbringing out a new concept of control hull which leads to consistent inner hulls and reduces the number of candidate points for establishing the MC, MI and MZ limacons. A new procedure for updating is also introduced. The results obtained for the

29、 circularity data reported in the literature are included in this part. In comparison with simplex search method, the proposed algorithm takes lesser time, leads to higher time saving for large datasets, and gives accurate results in absence of any convergence criterion. Part II of this paper deals

30、with the cylindricity evaluation from the form data 14.2. Circularity errorFig. 1 shows a point on the roundness prole represented by ri, yi. The gure also shows a limacon used for theNomenclatureFE farthest edgeLO edge of an outer control hull eideviation of ith point from assessment limaconLIedge

31、of an inner control hull iindex for data pointsLS least squaresri, yi polar coordinates of ith pointMC minimum circumscribingroradius of circle for assessment limaconMI maximum inscribingxo, yocenter coordinates of circle for assessmentMZMinimum zone limaconNEnearest edgeCffarthest centerVvertex on

32、a control hullCnnearest centerDform (circularity) error EAequiangular lineN. Venkaiah, M.S. Shunmugam / International Journal of Machine Tools & Manufacture 47 (2007) 122912361231assessment, as a curve representing the locus of foot of the perpendiculars drawn from origin O (pole) to the tangents of

33、 a circle whose radius is ro and center is Oo(xo, yo) 13. Fig. 2 shows the deviation of a given point Pi from the assessment limacon. For quantifying this deviation ei, another limacon passing through Pi may be assumed and the circle from which this limacon is obtained has the same center, but diffe

34、rent radius. It can be clearly seen that the separation between these two limacons is a measure of the deviation of point Pi from the assessment limacon. Interestingly, the radial distance between the two circles from which the limacons have been generated is also equal to the deviation ei, but the

35、point Pi falls outside themeasured point lying outside the assessment limacon is taken to be positive and a point inside is considered to have negative deviation. The circularity error (D) is, therefore, obtained as absolute sum of the maximum and minimum deviations.3. Control hullCrest and valley l

36、imacons pass through the extreme measured points. Therefore, it was considered appropriate to construct corresponding convex hulls. Outer hull was constructed as smallest convex hull enclosing all the measured points and inner hull was taken as largest empty convex hull. For each line connecting a v

37、ertex of the convex hull and the origin, a perpendicular line was drawn and equi-angular lines were constructed at the intersection of these perpendicular lines. It is observed that the algorithms 5,13 found in the literature for the convex inner hull are not consistent in constructing the same. Whi

38、le analyzing several alternatives for constructing unique inner convex hull, it is realized that the perpendi- cular lines drawn at each measured point yield a polygon, which can be directly used for constructing equi-angular diagrams. This polygon also results in the reduction of the number of cand

39、idate points for the construction of equi- angular diagrams and hence the subsequent computational effort.To differentiate between this polygon and the conven- tional convex hull used in computational geometry literature, the polygon obtained in the present work is referred to as control hull. The n

40、ew concept of forming a control hull followed in the present work is explained using Figs. 3(a) and 4(a). As shown in Fig. 3(a), at each point on the measured prole, a line is drawn perpendicular to the radial line joining the measured point and the origin, namely the instrument center. A smallest p

41、olygon isformedcorresponding circle. By convention, deviationofaFig. 1. Circularity data and limacon (for illustration only).Fig. 2. Deviation of a point from limacon.1232N. Venkaiah, M.S. Shunmugam / International Journal of Machine Tools & Manufacture 47 (2007) 12291236Fig. 3. Construction of fart

42、hest EA diagram: (a) outer control hull, (b) initial farthest EA edges, (c) updated hull and farthest EA edges, (d) farthest EA diagram and MC limacon.by the intersection of these lines such that all the measured points are conned within it. Such a polygon is referred to as outer control hull. Simil

43、arly, largest empty polygon obtained by the intersection of the perpendicular lines as shown in Fig. 4(a) is referred to as inner control hull. Interestingly, outer and inner control hulls are also convex in nature.4. MC limaconFig. 1 shows hypothetical prole of a circular feature. Outer control hul

44、l of the measured points is constructed as explained earlier. The edges of the hull such as LO1, LO2, LO3, LO4 and LO5 are established by the measured points P1, P3, P6, P8 and P11, respectively, as shown in Fig. 3(a).N. Venkaiah, M.S. Shunmugam / International Journal of Machine Tools & Manufacture

45、 47 (2007) 122912361233Fig. 4. Construction of nearest EA diagram: (a) inner control hull, (b) initial nearest EA edges, (c) updated hull and nearest EA edges, (d) nearest EA diagram and MI limacon.and FE34 have C23 and C34 as their centers, and for any point in the region enclosed by these two edge

46、s, the edge LO3 is the farthest. The outer hull is therefore updated by dropping the edge LO3. In case of the conventional convex hull, a vertex is dropped while updating 5,13. The edge LO5 is also dropped and a new hull is formed as shown in Fig. 3(c). New EA edges are formed for this updated hull

47、following the same procedure. The new edges FE12, FE24 and FE41 pass through a common center and therefore the procedure comes to end at this stage. The complete diagram as shown in Fig. 3(d) is referred to as farthest EA diagram. By taking the centers of the complete EA diagram, a number of circles

48、 can be drawn for the given data set. Out of these circles, one having the least radius is chosen to construct the MC limacon. The smallest circle thus obtained is tangential to the edges LO1, LO2 and LO4In the next step, for each pair of adjacent edges, equi- angular (EA) lines, such as EA12, EA23

49、etc are constructedatV12,V23, etc. as shown in Fig. 3(b). If a line EA23 isconsidered, it intersects with EA12 and EA34 at Cn (C12) and Cf (C34), respectively. The intersection point Cf, which is the farthest from the vertex V23, is the farthest center (C23). A circle drawn with this farthest center

50、 and with suitable radius will be tangential to the respective edges of the hull. For example, a circle with center Cf (C23) can be drawn tangential to the lines LO2 and LO3. It should be remembered that the circle being referred to here represents the circle from which the limacon is established. T

51、he limacon constructed from this circle would pass through points P3 and P6. The portion of the line EA23 beyond Cf, away from V23 is the farthest EA edge (FE23) correspond- ing to the edges LO2 and LO3 of the hull. Following the procedure outlined here, the farthest EA edges correspond- ing to all

52、pairs of edges of the hull are constructed as shown in Fig. 3(b). It is seen in Fig. 3(b) that a few edges have common farthest centers. For example, farthest edges FE23C124.of the hull with center atFor the sake of under-standing, the limacon established from this circle is also shown in Fig. 3(d),

53、 and this limacon passes through P1, P3, and P8.1234N. Venkaiah, M.S. Shunmugam / International Journal of Machine Tools & Manufacture 47 (2007) 122912365. MI limacondashed lines) diagrams are superimposed, as shown in Fig.5. The intersection points of these two diagrams are the candidate centers 5.

54、 The smallest possible circumscribing circle and largest possible inscribing circle with center at the intersection points of farthest and nearest EA diagrams are obtained and corresponding limacons are established. Such limacons will contain all the measured points between them. In case an intersec

55、tion point coincides with a common center of either the farthest or nearest EA edges, one of the limacons would be controlled by three points. Otherwise, both the limacons are controlled by two points each. The radial distance between these concentric lima- cons is found, and a pair having minimum r

56、adial separation gives the MZ limacons. The radial distance between these limacons is the circularity error. It is interesting to note that the difference between the radius values (ro) of the outer and inner circles corresponding to the respective limacons also denotes the MZ error. The center Oo o

57、btained by the intersection of the farthest and nearest EA diagrams as shown in Fig. 5 represents the center corresponding to the circles for MZ limacons. It may be noted in Fig. 5 that the outer limacon passes through two points P3 and P8, whereas the inner limacon passes through P5 and P10.Fig. 4(

58、a) shows the inner control hull of the measured points, constructed as explained earlier. This hull is used to construct the nearest EA diagram. The procedure for constructing the nearest EA diagram is similar to that of the farthest EA diagram, except that the nearest intersec- tion points are considered as end points of the nearest EA edges instead of farthest intersection points. Fig. 4(b) shows the nearest EA edges for the initial hull. The nearest EA edge between LI2 and LI3 is obtained by considering three EA lines namely, EA12, EA23 and EA34. The