Reference Algorithms for Chebyshev and One-Sided Data Fitting for Coordinate Metrology

This paper describes reference algorithms developed at the National Institute of Standards and Technology that fit geometric shapes to data sets according to Chebyshev, maximum-inscribed, and minimum-circumscribed criteria. Using an improved approach, we have developed more reliable reference algorithms for Chebyshev fitting for lines, planes, circles, spheres, cylinders, and cones. In the cases of circles, spheres, and cylinders, we also include maximum-inscribed and minimum-circumscribed fitting. In every case, we obtain the fit through an iteration that begins by using a (relatively easy) least-squares fit and then refine to the desired Chebyshev, maximum-inscribed, or minimum-circumscribed fit. We discuss why computing these fits is substantially more difficult than computing a least-squares fit, as the topography of the objective function prevents certain naive algorithms from working. We describe our choice of simulated annealing as a method that is general enough to be used for all the geometric shapes considered, requiring minimal customization for each shape. We outline steps taken for each geometric shape to reduce the number of fit parameters, thus improving the performance of the algorithms. We describe a suitable temperature reduction schedule that allows these algorithms to converge. We note cases of nonuniqueness related to maximum-inscribed fits. Finally we document test results showing the effectiveness of these algorithms against a battery of data sets with known solutions, against a limited number of exhaustive search results, against intercomparisons with other algorithms that provide for some of these fits, and against themselves by means of a repeatability study. We note that during intercomparisons, we found significant differences between our well-researched reference results and results obtained from algorithms that can be found in industrial use today.