|
|
|
|
| Re: Minimum area ellipse - quadratic optimisation? [message #47559 is a reply to message #47558] |
Thu, 16 February 2006 07:15   |
Paolo Grigis
Messages: 171
Registered: December 2003
|
Senior Member |
|
|
well, since you said that the center is fixed:
find the minimum area circle (which has the radius equal the distance
from the farthest point to the center, very easy) and squeeze it progressively
(along the direction perpendicular to the line connecting the center
to the farthest point) until you get a point outside the ellipse.
Trace one step back, and you're done!
Ciao,
Paolo
Olivia wrote:
> 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 #47631 is a reply to message #47553] |
Fri, 17 February 2006 09:28 |
Olivia
Messages: 16
Registered: February 2006
|
Junior Member |
|
|
>> 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
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
