# How to recognize ellipse/ellipsoid from random points? UN-weighted average?

Suppose we are getting random points in 2D (or 3D) which tend to be on ellipse (or ellipsoid). We can't guarantee points are uniformly distributed over ellipse (ellipsoid surface).

The task is to determine ellipse (ellipsoid) parameters, i.e. center location and semi-axes.

We can't take average, because it will be weighted. I mean if points will come preliminary from one side of ellipse, averaging will give wrong results.

So the question is how to UN-weight the average?

UPDATE

I think in the case of ellipse, the parameters can be determined by statistical quantities like moments. Can they?

-
See this question, this question, and perhaps also this question. You can also find a lot of stuff by googling "ellipse fitting". –  joriki Feb 4 '13 at 14:30

This paper gives a number of algorithms to find the "best" ellipse through given points, and the methods presented can be easily extended to the 3D case. In essence, most methods involve solving a least squared problem through matrix inversion or Singular value decomposition.

-
what a nice paper, thanks for the reference. With the problem actually sort of subtle like the way they explain, I can only wonder how Kepler managed to use Brahe's data to determine that the planetary orbits were ellipses. That said, I'm not so sure the methods are so easily extendable to 3D - in principle, yes, but 3D will open up a whole slew of new numerical problems that will easily fill a couple of publications. –  Ron Gordon Feb 5 '13 at 13:21
@rlgordonma - I'm going to assume Brahe's data had a lot less noise then some of the data in the paper. Also, Kepler didn't try to fit data to an equation, rather, he plotted the data and observed that this fit an "oval". See also here –  nbubis Feb 5 '13 at 14:10
thanks again for that link, very cool. –  Ron Gordon Feb 5 '13 at 16:05

I don't understand your concern with "unweighting".

Anyway, this site has code to fit both ellipses and ellipsoids, plus an explanation of the algorithms.

http://www.geometrictools.com/Documentation/LeastSquaresFitting.pdf

The fitting algorithms will still work fine even if the points are not uniformly distributed.

-
The section about ellipsoid is marked "to be written later" in this paper... –  Suzan Cioc Feb 9 '13 at 9:07