Clever Geek Handbook

How do I find a circle of minimum radius that spans all specified points?

Suppose there are about 1000 odd points on the plane.

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

Now from here, what can you do to find that circle with the minimum radius?

I want to generalize this for ellipses as soon as I understand how it can be done for circles.

Any reference to some "open source" would be helpful, so I can modify it for ellipses.

+2


source to share


2 answers


One option is the CGAL Computational Geometry Algorithm Library . It's open source, but it's also big - the biggest problem you'll run into, I suspect, is finding a needle in a haystack.



Of course (and this is kind of apologetic to Martin), you can easily find more focused options using Google. The second item on the list 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 that you don't know the word on Google anymore.

+2


source


This is called the minimum circumferential circle problem (I'm puzzled why your google search didn't find anything) and has been discussed here , here , here , and many other places.



+4


source






More articles:


All Articles