Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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. –  Joseph O'Rourke Jun 13 '11 at 12:55
    
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. –  shambu49 Jun 13 '11 at 13:20
    
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. –  Joseph O'Rourke Jun 13 '11 at 13:32
    
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. –  shambu49 Jun 13 '11 at 13:34
    
@Joseph Thanks, that one might just work! I'll just have to search the "best" one between the two. –  shambu49 Jun 13 '11 at 14:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.