circlefitting

Circle fitting is the process of determining a circle that best fits a set of data points. It is used in computer vision, pattern recognition, metrology, and geospatial analysis to recover circular features from noisy data or incomplete observations.

Formally, given a set of points (xi, yi), the goal is to find a center (a, b) and a radius r such that the points lie near the circle (x − a)² + (y − b)² = r². Fitting can proceed by minimizing different notions of residuals: the algebraic residuals, for which the distance is defined in a squared algebraic form, or the geometric residuals, which measure the true Euclidean distance from each point to the circle. The choice affects accuracy and computational effort.

Algebraic fitting methods attempt to linearize the problem. The Kasa method, a common starter approach, expands the circle equation to xi² + yi² − 2a xi − 2b yi + c = 0 with c = a² + b² − r² and solves for a, b, c via least squares, from which r is derived. Pratt and Taubin refinements improve bias and robustness by applying normalization or weighting constraints to the parameter estimates.

Geometric fitting seeks to minimize the actual geometric distances, typically requiring nonlinear optimization (Gauss–Newton or Levenberg–Marquardt). This approach generally yields more accurate circles but is computationally more intensive and relies on a good initial guess.

Applications often involve optional preprocessing to remove outliers (for example, using RANSAC) and may extend to fitting circles in three dimensions, which can require projection or specialized 3D circle fitting techniques.