1
$\begingroup$

Hello,

I'd like an algorithm for fitting an ellipse to a polygon. This polygon may be convex or concave. I've read about fitting an ellipse inside or outside a polygon (maximal and minimal of size, respectively), but that is not what I want. I'd like a best geometric fit to represent a polygon. I've tried general ellipse-fitting methods, but they just don't produce reasonable ellipsis. I've already tried algebraic, and geometric, least-squares methods.

I'd appreciate any help on this. Thanks in advance!

Improve this question
$\endgroup$
6
  • $\begingroup$ This is a heavily studied problem, and you have already examined the literature. I am not sure there is a magic bullet. Could you be more specific about what constitutes "a best geometric fit," and how the methods you tried have fallen short of that goal? Among the most frequently used methods is one due to Kasa: "A circle fitting procedure and its error analysis", IEEE Trans. Instrum. Meas., vol. 25, pp.8-14, 1976. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 13, 2011 at 12:55
  • $\begingroup$ The best geometric fit would be the one with minimal average distances. I've tried the direct approach described in the first paper (first link in my question), and the least-squares approach as described in the second link. I've run the MATLAB code with my data for Newton, Newton-Gauss, and Variable Projection methods. I could've drawn myself an ellipse which better fits my data :) Thanks for the reference, I'll check that soon. $\endgroup$
    – shambu49
    Commented Jun 13, 2011 at 13:20
  • $\begingroup$ I think the difficulty is that the literature concerns fitting an ellipse to scattered points, whereas you want to fit an ellipse to a polygon. A heuristic would be to interpolate between the largest inscribed and smallest circumscribed ellipses. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 13, 2011 at 13:32
  • $\begingroup$ Well I couldn't find the paper, but I've found the Kasa method. It's a simple algebraic method for fitting circles(!). I've read that iterative methods are more robust and accurate, which I prefer over computational complexity here. And since the least-squares method wasn't sufficient, I hardly believe that a simple algebraic method would suffice. $\endgroup$
    – shambu49
    Commented Jun 13, 2011 at 13:34
  • $\begingroup$ @Joseph Thanks, that one might just work! I'll just have to search the "best" one between the two. $\endgroup$
    – shambu49
    Commented Jun 13, 2011 at 14:44

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .