| Minimum area ellipse - quadratic optimisation? [message #47561] |
Thu, 16 February 2006 06:19  |
Olivia
Messages: 16
Registered: February 2006
|
Junior Member |
|
|
Dear All,
My aim is to fit an ellipse with a known center onto a distribution of
points, where all points have to be inside or on the ellipse, and the
ellipse chosen is of the minimum area.
I thought a brute force and not very clever way of doing this would be
to calculate the area taking each set of 3 points to solve the 3
remaining unknowns, (a, b, and orientation angle), in the ellipse
equation, and finding which one had the smallest area. But this
wouldn't work obviously as there would be no condition that all the
other points have to be inside the ellipse. I have read up on quadratic
optimization but have to admit I do not really understand the maths.
I posted on this topic before, but it is important that my ellipse
fitting method does not rely on convex hulls. I wrote a program which
does fit ellipses to the point distributions, but not the ellipses with
the minimum area.
I am sure the problem can't be as hard as I am finding it, and I am
feeling right now like drawing the 600 or so ellipses my program needs
myself! Any suggestions really would be very helpful. Thanks,
Olivia
|
|
|
|
| Re: Minimum area ellipse - quadratic optimisation? [message #47606 is a reply to message #47561] |
Tue, 21 February 2006 07:56  |
greg michael
Messages: 163
Registered: January 2006
|
Senior Member |
|
|
Thinking some more, I think I'd not pick the furthest point to choose
the axis, but find the direction with greatest moment (is that what
it's called?) - i.e. maximise sigma (r.cos(th-phi)), varying ph, with
r, th defining the point position from your centre. You might then pick
radii which enclose some sensible proportion of the points (90%) to get
better representative ellipses.
greg
|
|
|
|
| Re: Minimum area ellipse - quadratic optimisation? [message #47618 is a reply to message #47561] |
Mon, 20 February 2006 09:41 |
Paolo Grigis
Messages: 171
Registered: December 2003
|
Senior Member |
|
|
Olivia wrote:
>>> I posted on this topic before, but it is important that my ellipse
>>> fitting method does not rely on convex hulls.
>
>
>> Is there a special reason for this?
>
>
> There is a special reason. I am doing a project on galaxy cluster
> shapes, comparing the shapes of the clusters as determined by voronoi
> tesselations, and by the minimum area ellipses. So fitting ellipses to
> convex hulls would give a false comparison.
>
>
>> Perhaps
>> http://geometryalgorithms.com/Archive/algorithm_0107/algorit hm_0107.htm
>> could be of some help
>
>
> This looks like just the thing I am after. I don't think finding the
> center point and then finding the minimum area ellipse is a valid
> method, after experimenting with it today. I understand the idea of
> this fitting algorithm, but after reading the paper by Gaertner and
> Schoenherr I doubt if I would be able to right a program to fit the
> ellipses myself. Do you know of anyone who might have written one of
> these types of programs for IDL? Thanks very much for your idea, and
> help.
>
> Olivia
>
Well, if you don't want to write any new code, you could just do a
brute force optimization like this: suppose you have an efficient
function which, given whatever ellipse-parametrization you use
as input, tells you if all your points are inside the ellipse
or not (you should have that by now). Define a new function of the
ellipse parameters which returns the area of the ellipse if all
points are inside and a large number if at least one point is outside.
Then use a function minimizer (many exist, already implemented in IDL,
any which does not rely too much on the function being smooth will do)
to find the set of ellipse parameters which minimize your new function.
If you feed it reasonable starting guesses it should converge relatively
well and it might not be too slow. Maybe it is a bit of overkill,
but if you really want to avoid implementing other algorithms...
Ciao,
Paolo
|
|
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
