Least-squares fitting of circles and ellipses. (English) Zbl 0817.65008
The problems of fitting circles and ellipses to given points in the plane are discussed. Two fitting principles are considered: (i) The “geometric fit” where the sum of the squares of the (orthogonal) distances to the given points is minimized and (ii) the “algebraic fit” where the parameters of a circle or an ellipse are determined in the usual least- squares sense. The “geometric fit” is also considered for the parametric form of a circle or an ellipse, respectively.
Various algorithms for the “geometric fit” problems are compared. Further methods for the approximate solution of the “geometric fit” problem based on iterative “algebraic fit” solutions are discussed. Numerical examples are given. The paper contains outstanding and inspiring work in this area.
Various algorithms for the “geometric fit” problems are compared. Further methods for the approximate solution of the “geometric fit” problem based on iterative “algebraic fit” solutions are discussed. Numerical examples are given. The paper contains outstanding and inspiring work in this area.
Reviewer: H.Späth (Oldenburg)
MSC:
| 65D10 | Numerical smoothing, curve fitting |
Software:
ODRPACKReferences:
| [1] | V. Pratt,Direct Least Squares Fitting of Algebraic Surfaces, ACM J. Computer Graphics, Volume 21, Number 4, July 1987. |
| [2] | M. G. Cox, A. B. Forbes,Strategies for Testing Assessment Software, Technical Report NPL DITC 211/92, National Physical Laboratory, Teddington, UK., 1992. |
| [3] | G. H. Golub, Ch. Van Loan,Matrix Computations, 2nd ed., The Johns Hopkins University Press, Baltimore, MD., 1989. · Zbl 0733.65016 |
| [4] | D. Sourlier, A. Bucher,Normgerechter Best-fit-Algorithms für Freiform-Flächen oder andere nicht-reguläre Ausgleichs-Flächen in Parameter-Form, Technisches Messen 59 (1992), pp. 293–302. |
| [5] | H. Späth,Orthogonal least squares fitting with linear manifolds, Numer. Math., 48 (1986), pp. 441–445. · Zbl 0562.65008 · doi:10.1007/BF01389650 |
| [6] | L. B. Smith,The use of man-machine interaction in data fitting problems, TR CS 131, Computer Science Department, Stanford University, Stanford, CA, Ph.D. thesis, March 1969. |
| [7] | Y. V. Linnik,Method of least squares and principles of the theory of observations, Pergamon Press, New York, 1961. · Zbl 0112.11105 |
| [8] | C. L. Lawson,Contributions to the theory of linear least maximum approximation, UCLA, Los Angeles, Ph.D. thesis, 1961. |
| [9] | Fred L. Bookstein,Fitting conic sections to scattered data, Computer Graphics and Image Processing 9, (1979), pp. 56–71. · doi:10.1016/0146-664X(79)90082-0 |
| [10] | G. H. golub, V. Pereyra,The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate, SIAM J. Numer. Anal. 10, No. 2, (1973), pp. 413–432. · Zbl 0258.65045 · doi:10.1137/0710036 |
| [11] | M. Heidari, P. C. Heigold,Determination of Hydraulic Conductivity Tensor Using a Nonlinear Least Squares Estimator, Water Resources Bulletin, June 1993, pp. 415–424. |
| [12] | W. Gander, U. von Matt,Some Least Squares Problems, in Solving Problems in Scientific Computing Using Maple and Matlab, W. Gander and J. Hřebíček, eds., Springer-Verlag, 1993, pp. 251–266. |
| [13] | Paul T. Boggs, Richard H. Byrd and Robert B. Schnabel,A stable and efficient algorithm for nonlinear orthogonal distance regression, SIAM J. Sci. and Statist. Comput. 8 (1987), pp. 1052–1078. · Zbl 0637.65150 · doi:10.1137/0908085 |
| [14] | Paul T. Boggs, Richard H. Byrd, Janet E. Rogers and Robert B. Schnabel,User’s Reference Guide for ODRPACK Verion 2.01–Software for Weighted Orthogonal Distance Regression, National Institute of Standards and Technology, Gaithersburg, June 1992. |
| [15] | P. E. Gill, W. Murray and M. H. Wright,Practical Optimization, Academic Press, New York, 1981. |
| [16] | Gene H. Golub, Alan Hoffman, G. W. Stewart,A generalization of the Eckart-Young-Mirsky Matrix Approximation Theorem, Linear Algebra Appl., 88/89 (1987), pp. 317–327. · Zbl 0623.15020 · doi:10.1016/0024-3795(87)90114-5 |
| [17] | Walter Gander, Gene H. Golub, and Rolf Strebel,Fitting of circles and ellipses–least squares solution, Technical Report 217, Insitiut für Wisenschaftliches Rechnen, ETH Zürich, June 1994. Available via anonymous ftp from fip.inf.ethz.ch as doc/tech-reports/1994/217.ps. · Zbl 0817.65008 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
