Thread Subject: Best fit ellipse inside a non regular hexagon

Hi, i want to fit an ellipse that is teh best fit ellipse
inside a non regular hexagon. It means there would be an
ellipse that intersects every side of the hexagon at only
one point. Anybody have an idea about it?

"Mehmet OZTURK" <mehmetozturk@mathworks.com> wrote in
message <fusjd6$ae6$1@fred.mathworks.com>...
> Hi, i want to fit an ellipse that is teh best fit ellipse
> inside a non regular hexagon. It means there would be an
> ellipse that intersects every side of the hexagon at only
> one point. Anybody have an idea about it?

You could use fminsearch. The variables would be the 5
parameters that define an ellipse. Create an error function
that works out a measure of fit (perhaps by working out the
distance of each vertex of the hexagon to the nearest point
on the ellipse and sum for all points).

Peter Bone

"Mehmet OZTURK" <mehmetozturk@mathworks.com> wrote in message
<fusjd6$ae6$1@fred.mathworks.com>...
> Hi, i want to fit an ellipse that is teh best fit ellipse
> inside a non regular hexagon. It means there would be an
> ellipse that intersects every side of the hexagon at only
> one point. Anybody have an idea about it?

A general ellipse in two dimensions has 5
parameters. These parameters can be
described as:

The coordinates of the center of the ellipse.
This uses two parameters.

The lengths of the major and minor axes,
which also require a pair of parameters.

The tilt of the ellipse, perhaps as an angle.

You have 6 constraints, so this is an over
constrained problem. As such, we would
expect the general elliptical solution to
touch only 5 of the 6 sides of a general
hexagon.

A truly brute force approach might just
generate a large number of points on the
ellipse for any set of parameters. Then
use fmincon to maximize the area of the
ellipse, such that all the points fall inside
the hexagonal constraints. The 6 sides of
the hexagon can be written as linear
inequalities of course. So the problem
reduces to a set of nonlinear inequalities
in the ellipse parameters.

The area of the ellipse is just proportional
to the product of the major and minor axis
lengths. It should be pi*D1*D2/4, if D1
and D2 are the corresponding axis
"diameters".

I imagine there might be a simpler solution,
but this should probably work adequately.
You don't want me to actually think do you?

John

Tahnks all. Actually i know the center coordinates of the
ellips so 3 parameters rest to know.

I also think there might be a simpler solution and have to
find that solution. I will use this algorithm in sequantial
code therefore this algorithm might be fast and non-memory
consuming.

In article <fusnnt$980$1@fred.mathworks.com>, "Mehmet OZTURK" <mehmetozturk@mathworks.com> wrote:

> Tahnks all. Actually i know the center coordinates of the
> ellips so 3 parameters rest to know.
>
> I also think there might be a simpler solution and have to
> find that solution. I will use this algorithm in sequantial
> code therefore this algorithm might be fast and non-memory
> consuming.

So you wish to choose H so that

 (X-C)'*H*(X-C) = 1

subject to the (linear) constraint
system that

 A*X <= b

The objective is to maximize

 prod(eig(H))

I'm not at all sure there is a
trivial solution to be had.

John


--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous

John D'Errico <woodchips@rochester.rr.com> wrote in message
<woodchips-95D9AD.10403825042008@news.rochester.rr.com>...

>
> prod(eig(H))
>
This is det(H), that could be computed from its
coefficients. Not sure where it leads, but it could be an
useful information.

Bruno

"Mehmet OZTURK" <mehmetozturk@mathworks.com> wrote in message
<fusjd6$ae6$1@fred.mathworks.com>...
> Hi, i want to fit an ellipse that is teh best fit ellipse
> inside a non regular hexagon. It means there would be an
> ellipse that intersects every side of the hexagon at only
> one point. Anybody have an idea about it?
-----------
  You might try experimenting with an eigenvector approach. The idea is to
consider the vertices of the hexagon, or of any polygon for that matter, as a
"point cloud" and find the best fitting major axis in a least squares sense.
This is an eigenvector problem. Let the vertices be given by column vectors X
and Y.

 c = mean(X); d = mean(Y); % Center of ellipse is mean point
 [U,S,V] = svd([X-c,Y-d],0); % Use svd to find eigenvectors & eigenvalues
 n = length(X); % 6?
 a = S(1,1)/sqrt(n); b = S(2,2)/sqrt(n); % Get "best" axes' lengths
 p = V(1,1); q = V(2,1); % [p;q] is unit vector along major axis
 t = linspace(0,2*pi); % t is a parameter
 x = c+p*a*cos(t)-q*b*sin(t); % This is the parametric ellipse
 y = d+q*a*cos(t)+p*b*sin(t);

  The last two lines define an ellipse in terms of the parameter t, as t varies
from 0 to 2*pi. It certainly wouldn't in general have the intersection property
you described, but I seriously doubt if that is something you can expect to
achieve for random hexagons anyhow.

Roger Stafford

In article <fusjd6$ae6$1@fred.mathworks.com>,
Mehmet OZTURK <mehmetozturk@mathworks.com> wrote:
>Hi, i want to fit an ellipse that is teh best fit ellipse
>inside a non regular hexagon. It means there would be an
>ellipse that intersects every side of the hexagon at only
>one point. Anybody have an idea about it?

Intersects every side of the hexagon, or touches every side of
the hexagon? "intersects" implies that part of the ellipse might be
outside of the hexagon, but your Subject: says "inside"
--
  "What we have to do is to be forever curiously testing new
  opinions and courting new impressions." -- Walter Pater

Thanks for replies, i'm trying your solutions.
I also must define that this polygon has parallel opposite
sides. I draw a figure to describe this:
http://img373.imageshack.us/my.php?image=ellipsego0.jpg

"Mehmet OZTURK" <mehmetozturk@mathworks.com> wrote in
message <fusjd6$ae6$1@fred.mathworks.com>...
> Hi, i want to fit an ellipse that is teh best fit ellipse
> inside a non regular hexagon. It means there would be an
> ellipse that intersects every side of the hexagon at only
> one point. Anybody have an idea about it?

Fitting maximum volume ellipsoids inside polygons is a
classical convex optimization problems, i.e. it is
computationally tractable to do it.

If you use the matlab toolbox YALMIP together with an SDP
solver such as sdpt3, this code would suffice. (Not
necessarily the best approach though if you want to do it
your self on a machine with limited memory etc)

% Random instance
A = randn(10,2);
b = rand(10,1)*5;

% Parameterize ellipsoid as
% Pz+x0, ||z||<1
P = sdpvar(2,2);
x0 = sdpvar(2,1);

% Ax<b for all x in ellipsoids
% maximize over z gives
% ||Pai||+ai'x0 < bi
C = [];
for i = 1:length(b)
    C = [C,norm(P*A(i,:)')+A(i,:)*x0 < b(i)];
end

% Maximize determinant of P will maximize volume
solvesdp(C,-logdet(P))

% Plot
plot(A*sdpvar(2,1)<b)
hold on
ellipplot(P^(-2),1,'y',double(x0))