ON CHARACTERIZING CIRCULARITY Shou-Yan Chou Iowa Center for Emerging Manufacturing Technology Iowa State University Tony C. Woo Stephen M. Pollock Department of Industrial and Operations Engineering University of Michigan Technical Report 92-16 September 1992

On Characterizing Circularity* Shuo-Yan Chou Iowa Center for Emerging Manufacturing Technology Iowa State University Tony C. Woo Stephen M. Pollock Department of Industrial and Operations Engineering University of Michigan September 24, 1992 *This work was supported in part by a National Science Foundation grant DMC8903029 and by the University Research Program, Scientific Research Laboratory, Ford Motor Company.

Abstract This paper addresses issues which affect the assessment of circularity, including the derivation of a reference circle to which the circular feature is compared, the measure of similarity between the circular feature and its reference circle, and the representation of a circular feature. The assessment methods commonly employed in current practice are first reviewed. Efficient algorithms that compute the assessment of circularity are identified. Experiments with randomly generated data are performed to compare various criteria employed in these assessment methods. The difference in assessments can be attributed to the different definitions of geometric deviations in the different methods; it is therefore possible to choose assessment methods based on functionality. The notion of circularity is further decomposed into three types - internal, external, and strong - by which families of distance metrics are invoked to characterize similarity between the circular feature and its reference circle. ii

1 Introduction A circular feature in a mechanical object is one of the most basic geometric primitives. Other than its ease of specification - implicitly by a center and a radius or explicitly by its circumference - a circular feature has several functional advantages: it has uniform strength in any direction symmetric to the axis, it can be manufactured by a rotary tool, and its symmetry offers simplicity in assembly. However, due to imperfections introduced in manufacturing, a produced feature will not be truly circular. In practice, even though designs are toleranced with the intent of ensuring functionality, produced features are inspected to determined if a certain degree of circularity has been attained. A fundamental question then remains: Is one way of measuring circularity superior to another, particularly in regard to its relation to functionality? If so, under what circumstances? The lack of a clear answer to these questions is mainly due to inconsistencies between standards and practice. ANSI standards [2, 3] provide for both form tolerance and size tolerance. The circularity of a feature is considered to be in form tolerance if the width of an annulus containing the profile of the circular feature is narrower than the form tolerance. It is considered to be in size tolerance if this annulus lies entirely inside a size tolerance zone. Assigning a fixed width to an annular tolerance zone may not be functionally acceptable in practice. The reason is seen in the exaggerated example shown in Figure 1, where tolerance zones z1 and z2 are of the same width. Yet, the standards imply that, regardless of the radii, as long as the zones are of the same width, they yield the same circularity. The circularity of a feature can be defined to be the difference between its maximum and minimum radial ordinates [3]. Such a characterization is due to historical reasons: hard gages can only detect extreme radial ordinates. On the other hand, in employing soft gaging e.g. via coordinate measuring machines (CMMs), it is possible that those points on a circular feature that have extreme radial ordinates will escape being sampled. Moreover, it seems contradictory to have a characterization of circularity which depends solely on extreme radial ordinates while at the same time it is highly probable that points with extreme radial ordinates may not be identifiable. The assessment of circularity is further complicated by computational algorithms. The profile of a feature can be extrapolated into an ideal reference 1

Z2 Figure 1: Tolerance zones for circularity; zl = z2 circle. However, such a reference circle could be established by a number of criteria, such as: the minimum circumscribed circle; the maximum inscribed circle; the minmax circle1; the least absolute circle [29]; the least squares circle; or the variations of least squares circle [22]. Alternatively, the center of the reference circle can be established independently, such as by using the minimum area difference center method [18]. Thus, with a given tolerance specification on circularity, the same produced feature may be assessed to be in tolerance with respect to one reference circle but out of tolerance with respect to another. Indeed, there is no consensus among the practicianers on assessment methods [26]. As the competition for better products increases, so does the need for a more thorough examination of measurement practice. The standard for evaluating the performance of the coordinate measuring machines [2] provides specifications and procedures for ensuring the accuracy of the machines. In addition, calibration and compensation models for CMMs are employed to further enhance their performance [17, 27]. Yet, without an unambiguous characterization of circularity (or any other feature), no matter how precise of a measurement instrument is, the risk of rejecting good parts and accepting bad parts still exists [15]. The goal of this paper is to establish a mathematical framework upon which procedures for establishing reference circles, and metrics for measuring geometric deviation (from a reference circle), can be determined unam1The maximum deviation from the ideal circle is minimized. 2

biguously. In the next section, current practice for assessing circularity is presented. In section 3, issues concerning the notion of circularity and potential discrepancies among assessment procedures employed in current practice are examined in detail. Experiments are conducted to demonstrate the effects of employing different assessment procedures. In section 4, a general mathematical framework for characterizing circularity is proposed. Assessment methods employed in current practice are shown to be instances in this framework. Finally, families of metrics which yield different implications about functionality are discussed. 2 Current Practice in Soft Gaging Conventionally, the profile of a circular feature is measured diametrically. It is assumed that the distance between two parallel planes in contact with the workpiece yields a "diameter". The difference between the maximum diameter measured and the minimum diameter measured thus is presumed to give an indication of circularity. However, it is known [11, 23, 30] that such diametric measurements of circularity can be deceptive. For example, Figure 2 shows how the profile of a real feature which is decidedly not a circle may be surrogated incorrectly. Pedagogical counter-examples aside, an added difficulty with diametric measurements involves the determination of a realized feature's center: the centers computed from pairs of diametrically opposed points will not necessarily coincide. The profile of a circular feature can also be measured by tracing its perimeter with a stylus or a probe. One approach is to revolve the produced feature against a displacement transducer. An accurate reconstruction of the polar profile then will rely on the accurate centering of the feature, which can be laborious. A possible remedy is to employ a multiprobe which measures several coplanar points simultaneously; the errors of estimation of the position of the center can then be reduced with the extra information [21]. Nevertheless, all CMMs measure the radial ordinates of a circular feature about a virtual (i.e. estimated) center. The circularity of a feature is defined in current practice to be the difference between the maximum and the minimum radial ordinates of any measured polar profile, with respect to a pre-determined center. Such a measure of circularity can also be obtained algorithmically from a set of 3

c Figure 2: A Reuleaux triangle can be constructed by intersecting three arcs of radius D, the centers of which are 120~ apart. This produces the virtual circle C. Any two points obtained by making diametrical measurements of C will report a "diameter" of D; yet C is clearly not circular. points by computing two concentric circles: a circumscribed (circum-) and an inscribed (in-) circle. Conformance to circularity is then assessed by comparing the width of the annulus (determined by the two concentric circles) to a given tolerance. The differences in methods (and results) essentially depend upon the algorithm used to determine the center of these concentric circles. Four assessment procedures are commonly used [3, 13]: Minimum-radialseparation (MRS), Minimum-circumscribed-circle (MCC), Maximum-inscribedcircle (MIC), and Least-squares-circle (LSC), all illustrated in Figure 3. In each method2, a reference center is computed from P = {P1,P2,...,n}: the set of measured points [5, 9, 18]. Then the concentric circles circumscribing and inscribing all pi E P are computed with respect to the reference center. Efficient algorithms can be used to find reference circles, and thus reference centers, for the MRS, MCC, and MIC methods. Before presenting these, we note that an algorithm's practicality will be related to the time it needs for computation. Reference to Table 1, based on a 1 MIPS (million 2In British Standards, the Minimum-radial-separation is called the Minimumzone-center, the Minimum-circumscribed-circle is called the Ring-gage-center, and the Maximum-inscribed-circle is called the Plug-gage-center. 4

(a) (b) (c) (d) Figure 3: (a) MRS: Compute two concentric circles that are the least apart, and which enclose all the points. (b) MCC: Compute the minimum radius circum-circle, then compute the maximum in-circle concentric with the minimum circum-circle. (c) MIC: Compute the maximum radius in-circle, then, the minimum circum-circle concentric with the maximum in-circle. (d) LSC: Compute a least-squares circle, then compute the minimum circum-circle and the maximum in-circle concentric with the least-squares circle. 5

time^^ 10 102 103 0(n5 ) 101 sec. 10 sec. 115 days O(n4) 10-2 sec. 10 sec. 11.5 days 3 n3> -3 O(n3) 10 sec. 1 sec. 16.7 min. (n2)-4-2 O(n2)) 10 sec. 10 sec. 1 sec. O(n log n) 2.3 x 105 sec. 4.6 x 10 sec. 7 x 3sec. O(n) 10-5 sec. 1 ' sec. 163 sec. O(n) 10 sec. 10 sec. 10 sec. Table 1: Run time on a 1 MIPS computer as a function of algorithm complexity, n = number of measured points on a realized feature. instructions per second) computer, reveals the significance of having efficient algorithms. Procedures and Algorithms The Minimum-radial-separation procedure determines the reference center by computing an annulus, defined by a circumscribed and an inscribed circle of P, that has the minimum width, as shown in Figure 3 (a). Concentric circles that may have such a characteristic can be enumerated by choosing three points for one of the two concentric circles and one point for the other, or two points for each circle. Each of the 0(n4) pairs of concentric circles is then checked to see whether the annulus formed by them encloses all pi E P, which makes the total computation time 0(n5). It is shown by ]Le and Lee [18] that the number of candidates for checking can be reduced to O(k), where k is the number of intersections between the closest point Voronoi diagram and the farthest point Voronoi diagram of P. Additionally, for each candidate, there is, on average, a constant number of neighbors to be checked. The closest point and the farthest point Voronoi diagrams of P each takes O(n log n) time to compute. Consequently, the concentric circles needed for MRS can be computed in O(n log n + k) time3. A more detailed description of the algorithm is given in Appendix I. It is interesting to note 3In the worst case, k is equal to O(n2). 6

that a physical implementation of this concept uses a transparent template with scaled concentric circles: the template is shifted to a position where two selected concentric circles containing the entire measured polar profile are, presumably, the least distance apart. In the Minimum-circumscribed-circle procedure, the minimum circumcircle containing all pi E P is computed to determine the reference center, as shown in Figure 3 (b). Then, the maximum in-circle of P, which is concentric with the minimum circum-circle, is computed. Rather than examining all the 0(n3) candidates, the minimum circum-circle of P can be obtained in O(n) time with a linear programming formulation [20, 25]. Since the maximum concentric in-circle can be computed trivially in linear time, the MCC can be completed in linear time. The linear programming formulation is given in Appendix II. The procedure of Maximum-inscribed-circle is the reverse of the MCC: the maximum in-circle of pi E P is first computed to determine the reference center, as shown in Figure 3 (c). Then, the minimum circum-circle that is concentric with the maximum in-circle is computed. It is shown in [25] that examining the vertices in the closest point Voronoi diagram of P is sufficient for the identification of the maximum in-circle of P. As the closest point Voronoi diagram of P can be computed in O(nlog n) time and the minimum concentric circum-circle in O(n) time, the MIC can be completed in O(n log n) time. The algorithm is given in Appendix III. Since the sample points are from a feature that is, in some sense, "close" to circular, it is likely that are the vertices of their convex hull. Aggraval et al. [1] show that the Voronoi diagram of a convex polygon can be computed in 0(n) time, which means that in such a case, the maximum in-circle can be constructed in O(n) time. The Least-squares-circle procedure is commonly used because it is less sensitive to extreme radial ordinates and is closely related to similar measures in statistics, curve-fitting, etc. In this method, a circle is computed such that the sum of the squares of the radial ordinates between this circle and P is a minimum. The center of this least-squares circle is thus the reference center. The minimum circum- and the maximum in-circles which are concentric with this least-squares circle are then identified, as shown in Figure 3 (d). The computing of a least squares circle, however, is not as trivial as fitting a least squares line, for which a closed-form solution exists. Fitting a leastsquares circle requires solving a set of nonlinear simultaneous equations, or 7

Table 2: Time complexity of the four referenced-center methods. solving a nonlinear program [12]. Therefore, an approximation approach is usually used [3], in which an approximate least-squares center is first computed analytically (Appendix IV); with this center fixed, an approximate least-squares circle can also be computed analytically. Table 2 shows the time complexity required for the four methods (the time complexity for LSC is based on the approximation approach). 3 Discrepancies with Soft Gaging In this section, potential discrepancies in assessing circularity resulting from the use of the different assessment methods discussed above are demonstrated. To do this, we examine the yield - the fraction of circular features satisfying a given tolerance - obtained by using the different methods. The yield is determined by Monte-Carlo simulation: subjecting randomly generated data to each of the four methods. Note that by definition the MRS procedure will produce the tightest yield, since it creates the minimum annulus containing all points. Nonetheless, using this criterion is useful for comparing the relative strength of the other methods. The experimental design consisted of simulating 1000 random "circular" features. Each feature consists of 23 points distributed uniformly in angle with respect to an origin, and with radial distances of the points on the same circular feature following the normal distribution /(2.0, 0.01). These are used as input into each of the four assessment methods and then compared with circularity tolerances ranging from 0.02 to 0.06. The result is summarized in Figure 4. It can be seen in Figure 4 (a) that MRS gives the highest yield (as expected), while, in most of the cases, LSC has the lowest. When the tolerance is larger than 0.052, the yield resulting from LSC is higher than those from MIC and MCC. When the tolerance is smaller than 0.035, MIC is not 8

different from MCC. Figure 4 (b) depicts the yields computed for MIC, MCC and LSC, relative to the yield computed by MRS. As the tolerance gets tighter, the gap between the yield of the MRS procedure and the others gets wider. The above experiments illustrate one discrepancy in employing different assessment methods. One might be tempted to conclude that MRS gives the most optimistic yield. Perhaps for this reason it is stated in ANSI Standard B89.3.1, Measurement of Out-of-Roundness, that MRS should be employed unless otherwise specified [3]. However, a more subtle issue in choosing an assessment procedure needs to be addressed: whether the reference annulus obtained by MRS effectively indicates an attainable functionality of the circular feature. Consider a simple assembly of a hole and a shaft; the circularity of the hole is constrained so that a certain functionality generated from the coupling of the hole and the mating shaft can be ensured. The circularity of such a hole should be measured with respect to one of its inscribed circles, which represents a realization of the shaft. MRS may not accurately reflect such an attainable circularity. For example, under Maximum Material Condition (MMC), the conformance to the position and size of a hole is usually assessed with respect to the maximum in-circle of the hole. This is because the region of permissible locations of a circular feature grows larger as the assessed radius of the circular feature gets larger under MMC [4]. The relationship between size and position tolerances of a hole and the yield, with respect to various combinations of size and position tolerances, are illustrated in Appendix V. Since the maximum in-circle is employed for assessing the size of a hole and the minimum circum-circle for that of a shaft, a realization of the assembly may consist of a shaft which is of the same size as that of the maximum in-circle of its mating hole. This means that the attainable circularity of the hole should be relative to the maximum in-circle rather than the in-circle computed by MRS. Consequently, the width of the annulus containing the profile of the hole is generally wider than the one identified by MRS. In other words, MRS may over-estimate the circularity. Another concern involves the fundamental nature of the metric used to measure a circular feature for deviations from the ideal. The four assessment methods all employ as the measure of circularity the width of the annulus defined by concentric inscribed and a circumscribed circles of the circular feature. While the same metric is implied by all four methods, the intended 9

MRS 0.8 0. 6 0. 4 M\ MIC MCC 0.2 / -LSC _I --- —---- J --- —-------- t I Tolerance 0.03 0.04 0.05 0.06 Yield MICRS 0.8 0.6 LSC 0.4 0.2 0.02 0.03 0.04 0.05 0.06 Tolerance Figure 4: (a) Yield satisfying circularity as a function of circularity tolerance for 1000 random circular features, each of which contains 23 points, for MRS, MCC, MIC, and LSC methods. (b) Yield relative to MRS for MIC, MCC and LSC. 10

surface (a) (b) Figure 5: (a) Crevices penetrating beneath the predominant contact surface. (b) Protruding points with maximum radial ordinates affect the determination of the predominant contact surface. MCC is clearly preferred to MIC in order to assess rotational functionality functionalities, however, that might be distinguished by each of these methods, should differ. For example, consider the circularity of a rotating shaft. Crevices penetrating the contact surface, as shown in Figure 5 (a), might have little effect on its ability to rotate. Yet, if two concentric circles - regardless how their centers are determined - are fitted to enclose the profile, the crevices may not satisfy "circularity". Although these crevices can be ignored (by changing instrument filter settings, and/or by using a probe with a larger radius), the same cannot be said about protrusions illustrated by Figure 5 (b), which clearly do affect rotation. Finally, it does not appear to be reasonable to use one metric (e.g. L2 in LSC) to determine an "optimal" reference circle, and then to use another (Lo), which does not have any effect on the determination of this reference circle. 4 Characterization by Functionality The challenge of characterizing circularity lies in the ability to relate the various measures of circularity to different functionalities. In this section, circularity is first classified into three types - external, internal, and strong 11

- corresponding to the ideal features of a disc, a hole (the complement of a disc), and a circle. Assessment methods employed in current practice are then seen to be instances of these three. 4.1 Distances The notion of distance metrics, which are general measures of the "difference" between two sets of points, can be used to provide information on geometric similarity and subsequently circularity. A collection of distances d E D in a metric space is defined as {d E D: P x C(~) - Z}, (1) where P is a circular feature represented by a set of sample points {P1, P2, i, Pn}i and C(4)) is the class of all circles in Z2; the parameter (> consists of a center co and a radius r, and thus uniquely defines a circle. The distance from Pi to an ideal circle C, C E C(4), denoted by 6(pi, C), is defined as 6(pi, C) = min I pi- q, (2) qEC where || represents the Euclidean distance. From elementary geometry, ci, the point on C which is the closest to pi, lies on the ray which emanates from the center of C and passes through pi. This means that ci, pi, and co (the center of C, which we assume is available, by definition, when C is given) are collinear, as shown in Figure 6 (a). Furthermore, for each pi E P, there exists one and only one ci such that ci E C and pi - ci =(, C). (3) Given P and C, a set of points {cl, c2,..., c,} on C can be defined, which has a one-to-one correspondence with points of P, as shown in Figure 6 (b). This set of points on C is said to form a pseudo-circle, and is denoted by C. Note that C is an implicit function of its center co. The distance from ci, a point of C, to P can be defined similarly as 6(ci, P) =min | ci-pj. (4) pj EP It follows directly that (ci, P) =1 ci - pi, (5) 12

Fi Pi C* 0 Figure 6: (a) Points ci and cj on a circle. (b) A pseudo circle C defined by P. and therefore 8(ci, P) = 6(pi,C). (6) With the distance from a point to a set established, the distance from one set to another set can now be defined. The distance from P to C, denoted as d(P, C), is defined as d(P,C) = max 6(piC) (7) = max I pi - ci, (8) and the distance from C to P, d(C, P), is defined as d(C,P) = maxa(c, P) (9) P., max I ci - pi. (10) From equations (8) and (10), it is clear that d(P, C) = d(C, P). Finally, we note that it is possible to find a center cs of a "minimizing" ideal dC* by solving the equation d(C, P) = min (C, P) (11) EC CO 13

C(D) P, P (a) (b) (c) Figure 7: Ideal shapes for (a) external circularity, (b) internal circularity and (c) strong circularity. 4.2 Characterization and Its Instantiations External circularity measures the distance of a feature (the set P) from a circum-circle (the set C). The use of this concept implies that outward (away from the center of a circle) protuberances of a feature affect functionality, such as rotational stability. The MCC method can be considered to be an attempt to measure external circularity of a feature with respect to its minimum circum-circle, the identification of which can be formulated as min I Ci - Co, (12) d(P,D(Q))=O where D(() denotes the disc defined by circle C(()) including the areas enclosed. In other words, the ideal feature for external circularity is a disc rather than a circle, as shown in Figure 7 (a). The constraint d(P, D(~I)) = 0 guarantees that all pi E P lie inside C((). On the other hand, internal circularity, which measures the distance of a circular feature from an inscribed circle, implies that inward (toward the center of a circle) protuberances of a feature affect functionality. For exampile, the circularity of a hole to be mated with a shaft can be characterized by internal circularity. The MIC method can be considered as an attempt to 14

measure the internal circularity of a circular feature with respect to its maximum in-circle. The identification of the maximum in-circle can be formulated as max I| i - Co 1, (13) d(P,D(f))=o where D((I) denotes the complement of D(.T~), as shown in Figure 7 (b). The constraint d(P, D(1)) = 0 guarantees that all pi E P lie outside D(()). However, to ensure that C(<~) is an inscribed circle, the center of C(~t) must be constrained to lie inside the convex hull of P. Strong circularity is imposed on a circular feature if both the inward and outward protuberances are crucial to functionality. For example, in sealing fit, fluid is to be restrained by tight fitting. As the ideal shape for strong circularity is a circle, as shown in Figure 7 (c), a circle C(~), such that a certain distance between P and this circle is a minimum, is computed. MRS and LSC can be considered to be attempts to measure the strong circularity of a circular feature. In MRS, the annulus contains P and has the minimum width. Finding such an annulus is equivalent to finding a circle C(~) such that the Hausdorff distance between C(~) and P is minimized. By definition, the Hausdorff distance [7] between P and C is the metric dat such that d,(P, ) = d(C(, P) = max[d(P, C), d(C, P)]. (14) In other words, dH(P, C) captures the maximum of the distances from points in P to C and from points in C to P. Since d(P, C) = d(C, P), d.(P, C) can therefore be represented by either d(P, C) or d(C, P). The minimization of the width of the annulus containing P can subsequently be found by solving d m = min d (P, C(~)). (15) In LSC, the distance from P to C, denoted as dLs(P, C), is defined as dLs(P, ) = [6(pi, C)]2 (16) Pi EP = EIPi-ci 2. (17) i By such a definition, it is clear that dLs(C, P) is equal to dLs(P, ). A pseudo circle C(I), such that the sum of the squared distances between P 15

and C(() is a minimum, can be obtained by solving ds = mindLs(P, C(1)). (18) 4.3 Generalizing the Characterization Metrics other than those employed in the current practice are now examined. The sum-of-squares distance (dLs) employed in the LSC and the Hausdorff distance (de) employed in the MRS are known to be instances of a family of metrics, the general form of which is dp(x, y) = /IXl - ylP + x2 - Y2p + * * + \Xn - yn P (19) where x and y are two sets of points such that x = (xl,x2,..., n) and y = (Yl, Y2,..., yn) [28]. The metric space which results from these distance functions is also known as the Minkowski space. P and C correspond to two points in this space. The squared root of dLs can therefore be denoted as d2, and daH can be denoted as doo. A reference circle of P can be determined by using dp as a measure, and conformance to circularity between P and the reference circle can also be measured by dp. In general, varying the value of the measure-parameter p serves to impose different emphases or weights on the similarity between a feature and a reference circle. When dl is employed, the weights associated with individual feature point deviations from a reference circle are proportional to the magnitude of the deviation. As the value of p increases, the relative emphasis of larger deviations increases while that of smaller deviations decreases. By using Lo, only those points that deviate the most from the reference circle are weighted. This progressive shift of relative emphasis as the value of p varies is illustrated in Figure 8. In the figure, the deviations from an ideal circle are scaled with respect to the maximum deviation. Note that p does not have to be an integer. The effect of employing different dp can also be seen in the dispersion of the reference centers obtained by using them. The centers of 1000 random circular features, each of which consisted of 23 points, obtained from the (least) dl, d2, d3, and doo methods, respectively, and are plotted in Figure 9. The least-d2 method results in the least dispersion of center locations4. 16

importance 1 0.6 7//l 0.4 p=30 p=4 0. 0. X 0 relative deviation 0.2 0.4 0.6 0.8 i from maximum Figure 8: Relative importance of deviations with various p. Dispersion increases as p increases or decreases from two. The choice of p should be related to the effect deviation has on functionality. For example, when no point departing beyond a critical distance from a reference circle is acceptable, as in the sealing fit, doo should be used to assess the conformance to circularity. On the other hand, if the effect on functionality is simply proportional to the average magnitude of the deviation, dl should be employed. In addition to using different values of p, different restrictions on the circles also produce different realizations of reference circles. For example, as indicated above, circum-circles are used when the external circularity of a rotating shaft is to be characterized. Rather than fitting the minimum circum-circle to a feature, as in the MCC, a least-dp circum-circle, d+, such that d+(P, C) = min (E I p Pi -ci IP)/, (20) can be found. Equation (20) finds a circumscribed reference circle C such that the dp distance between the feature P and C is minimized. Similarly, instead of fitting the maximum inscribed circle as employed in 4This is due to the way the random circular features are generated. The dispersion of the least dp centers agrees with a known statistical property, in that d2 is the most appropriate choice for fitting data with normally distributed errors [24]. 17

L2 0.02 0.01 -0.02 -0o 0o ' ' 4 1. o0.02. '.;it.o...-0 01 0.02 -0.02 Linfinity L3 0.02.0.01 *. 3, '.. -0.02 -OQi1 b,.. 0.02 -0.02 Figure 9: Distribution of 1000 least dl, d2, d3, and do< centers. 23 sample points were used to generate each random "circular" feature. 18

the MIC, a least-dp in-circle can be fitted: dp(P, C) = min(m I pi - ci P)'p. (21) d(P,D(fl)=i0 Equation (21) finds an inscribed reference circle C such that the dp distance between the feature P and C is minimized. Note that minimizing d+ and dwith respect to co yields the circum- and in- circles which can be obtained from minimizing doo as in MRS. However, for p < oo, unlike fitting the minimum circum-circle or the maximum in-circle, which considers only point with extreme radial ordinates, fitting a least d+ or d- circle takes into account all the sample points. 5 Summary and Conclusion This paper shows that different assessment methods result in different conformance to circularity, and that different functional requirements may be characterized by these methods. The metrics behind these characterizations can subsequently be solicited to determine tolerance specifications, and conversely, to determine the firmware that should be employed for inspection. The radial difference between an in-circle and a circum-circles has been conventionally used for assessing circularity. We have shown that this is in fact using the least-doo measure of circularity. Similarly, other least-dp values computed with respect to individual least-dp reference circles can also be used as measures of circularity. It is noted that, the least-dp value between a circular feature and a reference circle, denoted as dp, is bounded by doo. This means that setting a tolerance on dp would be effective only if it is less than that set on do. Similar use of this set of metrics has been established for approximation and alignment problems in coordinate measurement techniques [14]. It is shown by Gupta [16] that different performance parameters of roller bearings correspond to different functions of out-of-roundness. The distance metrics in the Minkowski space can serve to measure these provided that the influence on functionality is a function of the radial distance from the ideal. For other types of relationship between geometric deviation and functionality, different sets of distance metrics may have to be employed. Other metrics capable of characterizing the difference between geometric shapes have been proposed. For example, the minimum area difference center 19

analyzed by Le and Lee [18] which finds two concentric circles with minimum area difference between them. Another is a method which represents an object by a turning function [6]. A turning function Op(s) of a feature P is the angle of counterclockwise tangents as a function of s, where s is measured along the circumference from a reference point on P. The distance between a feature P and a reference circle C is defined as dT(P, C) =II Op - EC IP= (J I ep(S)- Oc(S) IP ds)P. 4Oc(s) is clearly a straight line; the difference between Oc(s) and Op(s) can thus be computed easily. By minimizing dr(P, C), the conformance of P to (C can be computed. We can see that this is equivalent to finding dp when the integral is represented by a finite sum, as it must eventually if p is represented by a finite set of points. Finally, we stress that n, the number of sample points, affects the characterization and the assessment of circularity. As illustrated in Appendix VI, by employing different number of sample points, the estimated yield on circularity and the stability of the estimation will be different. The choice of an appropriate value of n, and its relation to statistical stability and consistency remains to be investigated. 20

References [1] Aggraval, A., L.J. Guibas, J. Saxe and P.W. Shor, "A Linear-Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon", Discrete & Computational Geometry, 4, 491-604, 1989. [2] ANSI Standard B89.1.12M, Methods for Performance Evaluation of Coordinate Measuring Machines, American Society of Mechanical Engineers, New York, 1985. [3] ANSI Standard B89.3.1, Measurement of Out-of-Roundness, American Society of Mechanical Engineers, New York, 1972. [4] ANSI Standard Y14.5M, Dimensioning and Tolerancing, American Society of Mechanical Engineers, New York, 1982. [5] Anthony, G.T. and M.G. Cox, "Reliable Algorithms for Roundness Assessment According to BS3730", Proc. of the Conference on Software for Co-ordinate Measuring Machines, ed. M.G. Cox and G.N. Peggs, National Physical Laboratory, 30-37, 1985. [6] Arkin, E.M., L.P. Chew, D.P. Huttenlocker, K. Kedem, and J.S. Mitchell, "An Efficiently Computable Metric for Comparing Polygonal Shapes", IEEE Trans. Pattern Analysis and Machine Intelligence, 13(3), 209-216, 1991. [7] Barnsley, M., Fractals Everywhere, Academic Press, 1988. [8] Chazelle, B. and H. Edelsbrunner, "An Optimal Algorithm for Intersecting Line Segments in the Plane", Proc. 29th Annual Symp. Founda. of Comp. Sci., 590-600, 1988. [9] Chetwynd, D.G., "Applications of Linear Programming to Engineering Metrology", Proc. Inst. Mech. Eng., 199(B2), 93-100, 1985. [10] Chetwynd, D.G., "On the Definition of Geometric Residuals", Proc. of the Conference on Software for Co-ordinate Measuring Machines, ed. M.G. Cox and G.N. Peggs, National Physical Laboratory, 42-46, 1985. 21

[11] Chandru, V. and R. Venkataraman, "Circular Hulls and Orbiforms of Simple Polygons", Proc. of the Second ACM-SIAM Symposium on Discrete Algorithms, 433-440, 1990. [12] Cox, M.G. and H.M. Jones, "An Algorithm for Least Squares Circle Fitting to Data with Specified Uncertainty Ellipses", IMA J of Numerical Analysis, 9, 285-298, 1989. [13] Farago, F.T., Handbook of Dimensional Measurement, Industrial Press, 2nd ed., 1982. [14] Goch, G., "Efficient Multi-Purpose Algorithm for Approximation and Alignment Problems in Coordinate Measurement Techniques", Annals of the CIRP, 39/1/1990, 553-556. [15] Government Industry Data Exchange Program, GIDEP Alert X1-A-88 -01, August 22, 1988. [16] Gupta, P.K., "On the Geometrical Imperfections in Cylindrical Roller Bearings", Journal of Tribology, 110, 13-18, 1988. [17] Kunzmann, H., E. Trapet, and F. Waldele, "A Uniform Concept for Calibration, Acceptance Test and Periodic Inspection of Coordinate Measuring Machines Using Reference Objects", Annals of the CIRP, 39/1/1990, 561-564. [18] Le, V.B., and D.T.Lee, "Out-of-Roundness Problem Revisited", IEEE Trans. Pattern Analysis and Machine Intelligence, 13(3), 217-223, 1991. [19] Lee, D.T., "Farthest Neighbor Voronoi Diagrams and Applications", Department of EECS, Northwestern University, Technical Report 80 -11-FC-04, November 1980. [20] Megiddo, N., "Linear Time Algorithms for Linear Programming in R3 and Related Problems", SIAM J. Comput., 12, 759-776, 1983. [21] Moore, D., "Design Considerations in Multiprobe Roundness Measurement", J. Physics, E: Sci. Instrum., 22, 339-343, 1989. [22] Moura, L. and R. Kitney, "A Direct Method for Least-Squares Circle Fitting", Computer Physics Communications, 64, 57-63, 1991. 22

[23] Osanna, P.H., N.M. Durakbasa, M. Cakmakci, and R. Obealander, "Cylindricity - A Well Known Problem and New Solutions", Int. J. Mach. Tools Manufact., 32(1/2), 91-97, 1992. [24] Powell, M.J.D., Approximation Theory and Methods, Cambridge University Press, 1981. [25] Preparata, F.P. and M. Shamos, Computational Geometry:An Introduction, Springer-Verlag, 1985. [26] Schreiber, R., "The Methods Divergence Dilemma", Manufacturing Engineering, 10, May 1990. [27] Shen, Y.L. and N.A. Duffie, "Uncertainties in the Acquisition and Utilization of Coordinate Frames in Manufacturing Systems", Annals of the CIRP, 40/1/1991, 527-530. [28] Shreider, Y.A., What is Distance?, University of Chicago Press, 1974. [29] Shunmugam, M.S., "Criteria for Computer-Aided Form Evaluation", Trans. ASME, J. of Engineering for Industry, 113, 233-238. 1991. [30] Srinivasan V., IBM T.J. Watson Research Laboratory, private communication. 23

APPENDICES I. Minimum Radial Separation To have an 0(n2) time algorithm, the closest point and farthest point Voronoi diagrams of P need to be computed first. Both diagrams can be constructed in O(nlogn) time with a divide-and-conquer scheme [19, 25]. Then, the two diagrams are merged to create the candidates for the centers of the circum- and in-circles of P. The intersection of these two diagrams are equivalent to that of O(n) line segments, which can be achieved with an algorithm by Chazelle and Edelsbrunner [8] in O(n log n + k) time, where k is the number of intersections between the two diagrams. The ( Voronoi) edges of the Voronoi diagrams are the loci of points equidistant to two given points. (For further clarification, see Appendix III.) The intersection of an edge from the closest point Voronoi diagram and an edge from the farthest point Voronoi diagram gives the center of a pair of circumand in-circles of P. The center of such a pair of circles with minimum radial separation is selected. II. Minimum Circumscribed Circle The algorithm developed by Megiddo [20] is based on a linear time algorithm that identifies a constrained version of the minimum circum-circle. As a constraint, the center of the circum-circle is forced to lie on a given line (e.g. the x-axis). The n points in P can be grouped into n/2 pairs, the perpendicular bisector of each of which is computed. The x-coordinates of the intersections of these perpendicular bisectors with the x-axis are called critical values. The optimum solution can be identified in linear time by using the median of these critical values. It can also be shown that the side of the given line on which the unconstrained center of the minimum circum-circle lies can be determined in linear time. By utilizing this result, it is shown that the unconstrained minimum circum-circle can also be constructed in linear time. III. Maximum Inscribed Circle To identify the maximum in-circle of a point set P in O(n log n) time, two procedures are employed. The closest point Voronoi diagram of P is first constructed by using a divide-and-conquer scheme [25]. Then, the candidates which are the vertices of the closest point Voronoi diagram are enumerated to establish the center of the maximum in-circle. 24

The closest point Voronoi diagram of P is a planar partition such that each region in the diagram contains the locus of the points that is closer to a point of P than to any other point of P. The edges of the diagram mark the locus of points equidistant to two neighbors. The edges of a Voronoi diagram intersect at vertices, which are equidistant to all the pairs of points of P contributing the Voronoi edges. The construction for an in-circle is immediate: Take a Voronoi vertex as the center; it must be equidistant to all the contributing nearest points. As there are as many in-circles as there are Voronoi vertices, the in-circle with the largest radius is chosen. IV. Least Squares Circle The approximate least-squares circle used in practice [3] is achieved in two steps. An approximate least-squares center (xc, yc) is first established from the set of sample points {(xi, y), (x2, Y2),..., (Xn, yn)}, where 2Exi 2Eyi xc = —, Ycn n Then, the radius of the least-squares circle is computed by finding the average distance from the sample points to the least-squares center (xc, Yc), which gives i ri Ei i/x - )2 + (, -yc)2 r- - n n It is clear that such a least-squares circle can be obtained in O(n) time. V. Size and Position Tolerances under MMC The relationship between size and position tolerances is illustrated in Figure 10, in which the size tolerance ranges from zero to a given value r. A cross-section of the truncated cone gives the position tolerance with respect to any particular realization of size tolerance. The MIC uses the maximum in-circle and thus leaves more room for deviation of the location of the center. On the other hand, the size of a shaft feature is typically assessed with MCC under CMM. The yield which is the percentage of realized features that satisfy both position and size tolerances under MMC is computed with respect to MRS, MCC, MIC, and LSC methods. In this context, the four methods refer to the four different center identification procedures. Since the tolerance on size is under MMC, the size of a hole feature is assessed by the maximum in-circle of the hole. For each method, yields are computed with size ranging 25

size tolerance position tolerance Figure 10: The relationship between position and size tolerances under MMC basis. from 1.95 to 1.99, size tolerance from 0.00 to 0.04, and position tolerance from 0.01 to 0.05. 1000 random circular features, each of which contains 23 points, generated as described in Section 3 are examined. The computed yields are illustrated in Figure 11. Each of the piecewise curves illustrates the yield of random circular features satisfying a fixed position tolerance but different size tolerance under MMC basis. In each curve, as size tolerance approaches to 2.0 (i.e. the mean of the radial distances of the sample points), the chance that an inscribed circle of a randomly generated circular feature is greater than the MMC size decreases. As a result, the probability of the random circular features satisfying both position and size tolerances decreases. It is seen that with the same specification on size and position tolerances, MIC gives the highest yield, while MCC has the lowest. VI. Effect with Various Sample Sizes The effect of employing different numbers n of sample points on the circular feature is illustrated in Figure 12. A thousand random circular features are generated for circular features with 7, 11, 13, 17, 23, and 29 sample points, respectively, and least-squares centers are computed for every individual circular features. The difference in the dispersion of these least-squares centers among circular features of different sample sizes can be easily seen, 26

Yield LSC 0.02 0.02 0.8 0.8 016 0.015 0.6 ~~~~~~~~0.015.6010.0156 0 6 0.6 0.4 \0.01 0 4 0.01 0.2 0.2 ize Size 1.96 1.97 1.98 1.99 Size 1.96 1.97 1.98 1.99 Yield MIC Yield MCC 1...... 1 0.02 0.8. 0.8 0.015 0.6 0.6 0.02 0.01 0.4 0.4 0.01 0.2' 0.2 0.01 Size Size 1.96 1.97 1.98 1.99 Size 1.96 1.97 1.98 1.99 Figure 11: Yield, which requires satisfying both position and size tolerances, as a function of size tolerance for LSC, MRS, MIC, and MCC. Each curve shows the yield computed with a fixed position tolerance but with various size tolerances under MMC basis. The sample is 1000 random circles as described in Section 3. 27

-0.02 -0o. b 0 0.02 -0.02 23 Points 0.02 o0.01 -0.02 -0.02 13 Points 0.01. 0.02. -0.02 -o.f a.. 0 0.02 -O. 01 i. -0. 0 0.02 0.02 0.01. -0 02 -oo0.01, *o; " 0:.02 -o0.02:. -0.02 Figure 12: Location of least squares centers as a function of n. 28

statistics 0,008- 0.006- number of.0 15 20 25 30 points Figure 13: The means p and standard deviation a of the distances between 1000 least-squares centers and the origin. in that the dispersion of centers decreases as the sample size increases. The means and standard deviations of the radial distances of the least-squares centers from the origin also exhibit such a reciprocal trend, as illustrated in Figure 13. The influence on the width of the annulus enclosing the circular feature by employing different numbers of sample points can also be observed. The annulus enclosing a circular feature is computed using LSC and compared to different tolerance specifications for circularity. The yield of satisfying circularity is computed for each set of circular features of the same number of sample points, as illustrated in Figure 14. Each of the curves corresponds to a specification of circularity tolerance, ranging from 0.02 to 0.06 with a 0.005 increment. As the number of sample points on a circular feature increases, the yield satisfying circularity decreases. This is due to the fact that the more (random) points that are generated, the more probable it is that larger deviations will appear. It is clear that the less dispersion there is in the least-squares-centers, the more stable the estimation of the center will be. This indicates that it is desirable to have a "large" number of samples on a circular feature. On the other hand, as the sample size increases, the estimated yield of the set of circular features satisfying circularity decreases, which suggests the use of a "small" number of samples. This trade off will be explored in future studies. 29

Figure 14: Yield requiring satisfying circularity as a function of n = number of sample points. The LSC method is employed to assess the conformance to circularity. Each curve corresponds to a specification of circularity tolerance. 30