Many drawing tools, such as iPad, have a function that when you are drawing a shape by hand, they will guess what it is, and make the best fit one to replace it. For example, if you draw a lopsided circle, it will produce a perfect one for it. In this project, i do that using the magic from linear algebra.
The used algorithm is based on the least square method. For example, to fit a circle,
we need to find out what c1, c2 and r are so that
is minimum for the given data (x1, y1),(x2, y2), . . . ,(xm, ym).
The above problem is nonlinear, which is hard to solve. But we can approximate it by rewriting (1) with
for c3 = r^2 − (c1)^2 - (c2)^2 , and making c1, c2, c3 independent variables.
To transform the min f(c1,c2,c3) into matrix form. Let
,
The original problem is to solve an over-determinded system, Ax = b.
The problem is also called a least square problem, which can be solved by the normal equation (A^T) A x = (A^T) b.
-
to find best fitting circle:
uses "numpy.linalg.lstsq" to solve the least square problem. -
to find best fitting ellipse:
using least square algorithm with the formula
" c1 x^2 + c2 xy + c3 y^2 + c4 x + c5 y = 1 ".
The formula can actually fit all kinds of curves from conic section.
- example1:
- example2:
- example3:
- example1:
- example2:
- example3:
- find the minimum enclosing circle for the given points.
- example1:
- example2:
- example3:
- example4:
