×

Fitting of circles and ellipses least squares solution. (English) Zbl 0826.65010

Moonen, Marc (ed.) et al., SVD and signal processing III: algorithms, architectures and applications. Based on contributions presented at the 3rd international workshop on SVD and signal processing, Leuven (Belgium), 22-25 August 1994. Amsterdam: Elsevier. 349-356 (1995).
Summary: Fitting ellipses to given points in the plane is a problem that arises in many application areas, e.g. computer graphics, coordinate metrology, petroleum engineering, statistics. In the past, algorithms have been given which fit circles and ellipses in some least squares sense without minimizing the geometric distance to the given points.
In this article, we first present algorithms that compute the ellipse, for which the sum of the squares of the distances to the given points is minimal. Note that the solution of this nonlinear least squares problem is generally expensive. Thus, in the second part, we give an overview of linear least squares solutions which minimize the distance in some algebraic sense. Given only a few points, we can see that the geometric solution often differs significantly from algebraic solutions.
Third, we refine the algebraic method by iteratively solving weighted linear least squares. A criterion based on the singular value decomposition is shown to be essential for the quality of the approximation to the exact geometric solution.
For the entire collection see [Zbl 0817.00020].

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65D10 Numerical smoothing, curve fitting
PDFBibTeX XMLCite