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.

Lazer
  • 90,700
  • 113
  • 281
  • 364
  • Wikipedia article you've linked mentions "*rotating calipers* method for computing the width and diameter of a point set". – jfs Oct 03 '09 at 09:56

2 Answers2

5

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
  • 124,830
  • 17
  • 198
  • 235
  • 10
    Isn't not-knowing-the-right-words-to-Google-for part of the reason why stack overflow was created? –  Oct 03 '09 at 10:01
  • does anyone know some implementation (i mean code), to which I can refer to? – Lazer Oct 03 '09 at 11:57
  • Take a look at this question: http://stackoverflow.com/questions/2395178/given-n-points-in-a-3d-space-how-to-find-the-smallest-sphere-that-contains-thes/14979145#14979145 – Hbf Feb 20 '13 at 20:54
2

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.

  • @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 Oct 04 '09 at 22:08
  • @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. –  Oct 05 '09 at 11:52