Least-squares circle fitting - Revision history

A WASSERMANN at 20:45, 1 January 2011

2011-01-01T20:45:31Z

← Older revision		Revision as of 20:45, 1 January 2011
Line 1:		Line 1:
	~~<source lang="list"></source>~~
	This is an implementation of the linear least-squares algorithm by Coope (1993) for circle fitting.		This is an implementation of the linear least-squares algorithm by Coope (1993) for circle fitting.
	<jsxgraph width="600" height="600">		<jsxgraph width="600" height="600">

A WASSERMANN at 10:19, 26 November 2010

2010-11-26T10:19:59Z

← Older revision		Revision as of 10:19, 26 November 2010
Line 1:		Line 1:
			<source lang="list"></source>
	This is an implementation of the linear least-squares algorithm by Coope (1993) for circle fitting.		This is an implementation of the linear least-squares algorithm by Coope (1993) for circle fitting.
	<jsxgraph width="600" height="600">		<jsxgraph width="600" height="600">

A WASSERMANN at 10:04, 26 November 2010

2010-11-26T10:04:18Z

← Older revision		Revision as of 10:04, 26 November 2010
Line 55:		Line 55:
	</jsxgraph>		</jsxgraph>
	===The underlying JavaScript code===		===The underlying JavaScript code===
	<~~code~~ javascript n>		<source lang="javascript">
	var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});		var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});
	var i, p = [], angle, co, si, delta = 0.8;		var i, p = [], angle, co, si, delta = 0.8;

A WASSERMANN at 10:03, 26 November 2010

2010-11-26T10:03:42Z

← Older revision		Revision as of 10:03, 26 November 2010
Line 55:		Line 55:
	</jsxgraph>		</jsxgraph>
	===The underlying JavaScript code===		===The underlying JavaScript code===
	<~~source lang="~~javascript">		<code javascript n>
	var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});		var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});
	var i, p = [], angle, co, si, delta = 0.8;		var i, p = [], angle, co, si, delta = 0.8;

A WASSERMANN at 18:25, 5 November 2010

2010-11-05T18:25:18Z

← Older revision		Revision as of 18:25, 5 November 2010
Line 36:		Line 36:
	}		}

	// Now, the general ~~lineat~~ least-square fitting problem		// Now, the general linear least-square fitting problem
	// min_z \|\| M*z - y\|\|_2^2		// min_z \|\| M*z - y\|\|_2^2
	// is solved by solving the system of linear equations:		// is solved by solving the system of linear equations
	// (M^TM) z = (M^T*y)		// (M^TM) z = (M^T*y)
	// with Gauss elimination.		// with Gauss elimination.
Line 91:		Line 91:
	}		}

	// Now, the general ~~lineat~~ least-square fitting problem		// Now, the general linear least-square fitting problem
	// min_z \|\| M*z - y\|\|_2^2		// min_z \|\| M*z - y\|\|_2^2
	// is solved by solving the system of linear equations:		// is solved by solving the system of linear equations
	// (M^TM) z = (M^T*y)		// (M^TM) z = (M^T*y)
	// with Gauss elimination.		// with Gauss elimination.

A WASSERMANN at 16:09, 5 November 2010

2010-11-05T16:09:45Z

← Older revision		Revision as of 16:09, 5 November 2010
Line 4:		Line 4:
	var i, p = [], angle, co, si, delta = 0.8;		var i, p = [], angle, co, si, delta = 0.8;

	// ~~Randomn~~ points are constructed which lie roughly on a circle		// Random points are constructed which lie roughly on a circle
	// of radius 4 having the origin as center.		// of radius 4 having the origin as center.
	// delta*0.5 is the maximal distance in x- and y- direction of the random		// delta*0.5 is the maximal distance in x- and y- direction of the random
Line 25:		Line 25:
	// ...		// ...
	// x_n, y_n, 1		// x_n, y_n, 1
	// where x_i, y_i is the ~~postion~~ of point p_i		// where x_i, y_i is the position of point p_i
	// The vector y of length n consists of		// The vector y of length n consists of
	// x_ix_i+y_iy_i		// x_ix_i+y_iy_i
Line 59:		Line 59:
	var i, p = [], angle, co, si, delta = 0.8;		var i, p = [], angle, co, si, delta = 0.8;

	// ~~Randomn~~ points are constructed which lie roughly on a circle		// Random points are constructed which lie roughly on a circle
	// of radius 4 having the origin as center.		// of radius 4 having the origin as center.
	// delta*0.5 is the maximal distance in x- and y- direction of the random		// delta*0.5 is the maximal distance in x- and y- direction of the random
Line 80:		Line 80:
	// ...		// ...
	// x_n, y_n, 1		// x_n, y_n, 1
	// where x_i, y_i is the ~~postion~~ of point p_i		// where x_i, y_i is the position of point p_i
	// The vector y of length n consists of		// The vector y of length n consists of
	// x_ix_i+y_iy_i		// x_ix_i+y_iy_i
Line 101:		Line 101:
	z = JXG.Math.Numerics.Gauss(B, c);		z = JXG.Math.Numerics.Gauss(B, c);

	// Finally, we can read of the coordinates [xm, ym] of the center		// Finally, we can read from the solution vector z the coordinates [xm, ym] of the center
	// and the radius r ~~from z:~~		// and the radius r and draw the circle.
	var xm = z[0]*0.5;		var xm = z[0]*0.5;
	var ym = z[1]*0.5;		var ym = z[1]*0.5;

A WASSERMANN at 16:08, 5 November 2010

2010-11-05T16:08:40Z

← Older revision		Revision as of 16:08, 5 November 2010
Line 46:		Line 46:
	z = JXG.Math.Numerics.Gauss(B, c);		z = JXG.Math.Numerics.Gauss(B, c);

	// Finally, we can read of the coordinates [xm, ym] of the center		// Finally, we can read from the solution vector z the coordinates [xm, ym] of the center
	// and the radius r ~~from z:~~		// and the radius r and draw the circle.
	var xm = z[0]*0.5;		var xm = z[0]*0.5;
	var ym = z[1]*0.5;		var ym = z[1]*0.5;

A WASSERMANN at 16:03, 5 November 2010

2010-11-05T16:03:22Z

@@ Line 4: / Line 4: @@
 var i, p = [], angle, co, si, delta = 0.8;
 brd.suspendUpdate();
 for (i=0;i<100;i++) {
@@ Line 15: / Line 73: @@
 brd.unsuspendUpdate();
+// Having constructed the points, we can fit a circle
-var M = [], y = [], MT, B, c, coeffs, len;
+// through the point set, consisting of n points.
-len = p.length;
+// The (n times 3) matrix consists of
-for (i=0;i<len;i++) {
+//   x_1, y_1, 1
      M.push([p[i].X(), p[i].Y(), 1.0]);
      y.push(p[i].X()*p[i].X() + p[i].Y()*p[i].Y());
+}
 MT = JXG.Math.transpose(M);
 B = JXG.Math.matMatMult(MT, M);
 c = JXG.Math.matVecMult(MT, y);
-coeffs = JXG.Math.Numerics.Gauss(B, c);
+z = JXG.Math.Numerics.Gauss(B, c);
 brd.create('circle',[ [xm,ym], r]);
-</jsxgraph>
+</source>
 ===References===
 * Coope, I.D., ''Circle fitting by linear and nonlinear least squares'', Journal of Optimization Theory and Applications Volume 76, Issue 2, New York: Plenum Press, February 1993

A WASSERMANN at 15:47, 5 November 2010

2010-11-05T15:47:36Z

← Older revision		Revision as of 15:47, 5 November 2010
Line 1:		Line 1:
			This is an implementation of the linear least-squares algorithm by Coope (1993) for circle fitting.
	<jsxgraph width="600" height="600">		<jsxgraph width="600" height="600">
	var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});		var brd = JXG.JSXGraph.initBoard('jxgbox',{boundingbox:[-5,5,5,-5], keepaspectratio:true});
			var i, p = [], angle, co, si, delta = 0.8;

	~~var i, p = [], angle, co, si, delta = 0.8;~~

	brd.suspendUpdate();		brd.suspendUpdate();
	for (i=0;i<50;i++) {		for (i=0;i<100;i++) {
	angle = Math.random()2Math.PI;		angle = Math.random()2Math.PI;

A WASSERMANN at 15:46, 5 November 2010

2010-11-05T15:46:25Z

← Older revision		Revision as of 15:46, 5 November 2010
Line 30:		Line 30:
	var r = Math.sqrt(coeffs[2]+xmxm+ymym);		var r = Math.sqrt(coeffs[2]+xmxm+ymym);
	brd.create('circle',[ [xm,ym], r]);		brd.create('circle',[ [xm,ym], r]);



	</jsxgraph>		</jsxgraph>
			===References===
			* Coope, I.D., ''Circle fitting by linear and nonlinear least squares'', Journal of Optimization Theory and Applications Volume 76, Issue 2, New York: Plenum Press, February 1993

	[[Category:Examples]]		[[Category:Examples]]
	[[Category:Statistics]]		[[Category:Statistics]]