Abstract
This work addresses the problem of enclosing given data points between two concentric circles (spheres) of minimum distance whose associated annulus measures the out-of-roundness (OOR) tolerance. The problem arises in analyzing coordinate measuring machine (CMM) data taken against circular (spherical) features of manufactured parts. It also can be interpreted as the “geometric” Chebychev problem of fitting a circle (sphere) to data so as to minimize the maximum distance deviation. A related formulation, the “algebraic” Chebychev formula, determines the equation of a circle (sphere) to minimize the maximum violation of the equation by the data points. In this paper, we describe a linear-programming approach for the algebraic Chebychev formula that determines reference circles (spheres) and related annuluses whose widths are very close to the widths of the true geometric Chebychev annuluses. We also compare the algebraic Chebychev formula against the popular algebraic least-squares solutions for various data sets. In most of these examples, the algebraic and geometric Chebychev solutions coincide, which appears to be the case for most real applications. Such solutions yield concentric circles whose separation is less than that of the corresponding least-squares solution. It is suggested that the linear-programming approach be considered as an alternate solution method for determining OOR annuluses for CMM data sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
American Society of Mechanical Engineers, Measurement of Out-of Roundness, ANSI B89.3.1–1972, New York (1972).
Anthony, G.T., Anthony, H.M., Bittner, B., Butler, H.P., Cox, M.G., Drieschner, R., Elligsen, R., Forbes, A.B., Gross, H., Hannaby, S.A., Harris, P.M., and Kok, J., “Chebychev Best-Fit Geometric Elements,” NPL Report DITC 221/93, National Physical Laboratory, Teddington, United Kingdom (1993).
Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., “The Quickhull Algorithm for Convex Hulls,” University of Minnesota, Minneapolis (1995).
Boggs, P.T., Byrd, R.H., Rogers, J.E., and Schnabel, R.B., “User's Reference Guide for ODRPACK Version 2.1- Software for Weighted Orthogonal Distance Regression,” National Institute of Standards and Technology, Gaithersburg, MD (1992).
Butler, B.P., Forbes, A.B., and Harris, P.M., “Algorithms for Geometric Tolerance Assessment,” NPL Report DITC 228/94, National Physics Laboratory, Teddington, United Kingdom (1994).
Carr, K. and Ferreira, P., “Verification of Form Tolerances, Part I: Basic Issues, Flatness, and Straightness, and Part II: Cylindricity, Circularity, and Straightness of a Median Line,” Ford Technical Report #SR–94–14, Ford Research Laboratory, Flint, MI (1994).
Chetwynd, D.G., “Applications of Linear Programming to Engineering Metrology,” in Proceedings, Institute of Mechanical Engineers, Vol. 199, No. B2, pp. 93–100 (1985).
Chou, S.-Y., Woo, T.C., and Pollock, S.M., “On Characterizing Circularity,” Department of Industrial and Operations Engineering, The University of Michigan, Ann Arbor (1993).
Elzinga, D.J. and Hearn, D.W., “The Minimum Covering Sphere Problem,” Management Science, Vol. 19, No. 1, pp. 96–104 (1972).
Etesami, F. and Qiao, H., “Analysis of Two-Dimensional Measurement Data for Automated Inspection,” Journal of Manufacturing Systems, Vol. 7, No. 3, pp. 223–232 (1988).
Feng, S.C. and Hopp, T.H., “A Review of Current Geometric Tolerancing Theories and Inspection Data Analysis Algorithms,” NISTIR 4509, National Institute of Standards and Technology, Gaithersburg, MD (1991).
Gander, W., Golub, G.H., and Strebel, R., “Least-Squares Fitting of Circle and Ellipses,” BIT, Vol. 24, pp. 560–578 (1994).
Gass, S.I., Linear Programming, McGraw-Hill Book Company, New York (1985).
Harary, H., Dufraigne, J.-O., Chollet, P., and Clement, A., “Probe Metrology and Probing with Coordinate Measuring Machines,” International Journal of Flexible Automation and Integrated Management, Vol. 1, No. 1, pp. 59–70 (1992).
Harary, H., Buchard, C., L' Heritier, P., Dufraigne, J.-O., and Chollet, P., “Some Considerations for a Measurement Strategy for Circular Features,” in Proceedings of the 1994 Annual Meeting of the American Society for Precision Engineering, pp. 218–221 (1994).
Hearn, D.W. and Vijay, J., “Efficient Algorithms for the (Weighted) Minimum Circle Problem,” Operations Research, Vol. 30, No. 4, pp. 777–795 (1982).
Hopp, T.H. and Reeve, C.A., “An Algorithm for Computing the Minimum Covering Sphere in any Dimension,” NISTIR 5831, National Institute of Standards and Technology, Gaithersburg, MD (1996).
Jones, B.A. and Schnabel, R.B., “A Comparison of Two Sphere Fitting Methods,” in Proceedings of the Instrumentation and Measurement Technology Subgroup of the IEEE, Boulder, CO (1986).
Le, V.-B. and Lee, D.T., “Out-of-Roundness Problem Revisited,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, No. 3, pp. 217–223 (1991).
Lee, D.T. and Drysdale, R.L., III, “Generalization of Vornoi Diagrams in the Plane,” SIAM Journal of Computing, Vol. 10, No. 1, pp. 73–87 (1981).
Megiddo, N., “Linear-Time Algorithms for Linear Programming in R3 and Related Problems,” SIAM Journal of Computing, Vol. 12, No. 4, pp. 759–776 (1983).
Phillips, S.D., “Performance Evaluation,” Chapter 7 in Coordinate Measuring Machines and Systems, J. Bosch (Ed.), Marcel Dekker, New York (1995).
Phillips, S.D., Borchardt, B., and Caskey, G., “Measurement Uncertainty Considerations for Coordinate Measuring Machines,” NISTIR 5170, National Institute of Standards and Technology, Gaithersburg, MD (1993).
Preparata, F.P. and Shamos, M.I., Computational Geometry, Springer-Verlag, New York (1985).
Shannos, M.I. and Hoey, D., “Closest-Point Problems,” in Proceedings of the 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Long Beach, CA, pp. 151–162 (1975).
Schrage, L., User's Manual: Linear, Integer, and Quadratic Programming with Lindo, 4th ed., Scientific Press, South San Francisco, CA (1989).
Zhou, J.L., Tits, A.L., and Lawrence, C.T., “FFSQ Software,” Electrical Engineering Department, University of Maryland, College Park (1995).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gass, S.I., Witzgall, C. & Harary, H.H. Fitting Circles and Spheres to Coordinate Measuring Machine Data. International Journal of Flexible Manufacturing Systems 10, 5–25 (1998). https://doi.org/10.1023/A:1007996916604
Issue Date:
DOI: https://doi.org/10.1023/A:1007996916604