views:

398

answers:

2

Suppose I have some 1000 odd points on a plane.

Then, what I think could be done is to discard the points that do not affect the radius of the circle in any way - the points through which the convex hull does not pass [using one of the several algorithms]. This leaves us with points that do matter.

Now from here on, what can be done to find that minimum radius circle?

I am looking to generalize this for ellipses once I understand how it can be done for circles.

Any link to some "public source code" would be helpful, so that I can modify it for ellipses.

+4  A: 

This is known as the Minimal Enclosing Circle problem (I'm puzzled why your google search didn't show up anything), and discussed here, here, here, and in many other places.

Martin v. Löwis
Isn't not-knowing-the-right-words-to-Google-for part of the reason why stack overflow was created?
Steve314
does anyone know some implementation (i mean code), to which I can refer to?
Lazer
+2  A: 

One option is the CGAL Computational Geometry Algorithms Library. It is open source, but it is also large - the biggest problem you'll have, I suspect, is finding the needle in the haystack.

Of course (and this is partly in apology to Martin), you can easily find more focussed options using Google. The second item listed looked OK when I tried, if you don't mind Prolog, and there was at least one C example and one Javascript on the first page of results. And you can hardly claim not to know the words to Google for any more.

Steve314
@Steve thanks for the excellent link. Actually, I found what I need, but I am not able to compile the sample code at http://www.cgal.org/Manual/3.5/examples/Min_circle_2/min_circle_2.cpp I am getting this: http://imgur.com/h9TYC.jpg as you can see I've put the code right in the include directory to let the code find the headers(it gave the same erros anywhere else too). What am I doing wrong?
Lazer
@eSKay - sorry, I don't know that much about CGAL. I was aware of it from watching part of http://www.youtube.com/watch?v=3DLfkWWw_Tg - found in a search for computational geometry stuff - that's all.
Steve314
@Steve314 okay, thanks for the libraries anyways.
Lazer