Smallest circle around N points

[JÞB]

---

Darin.K wrote:

The true genius on my part was putting in that little bug so you had to sift through the code and really understand what was going on.  This way it isn't just a black box.  That's my story and I am sticking to it. 

---

OK I guess you are entitled to the story!  I won't confuse it with fact though. 

[ben64]

That was a really fun task to implement and it shure dust off some math for a lot of us. Congratulation to Darin for his code, it is really clean and effective. Actually I was really curious to see the Elzinga-Hearn algorithm in action so I created this VI (min Circle1) with a delay between the iterations to actually see what's going on. I borrowed from Darin his idea for generating random numbers (thanks to you). The code probably also need some cleanup....eventually.

Ben

[murphyfields]

Great job on the original problem.

I have a similar problem.  I have a set of N points, and I want the smallest circle that encloses them, but with a few modifications...

I know that all of the points lie inside the unit circle (distance from the origin is less than or equal to 1)

The resulting smallest circle must also be completely inside the unit circle.  You would think that this would be automatic, but if you can imagine just three points, two of which ar on the unit circle near the right side and one at the origin.  The smallest circle would hit all three points but part of the solution circle will be outside the unit circle.  The only solution that encompasses all three points but remains in or on the unit circle is the unit circle.

I will provide some examples if necessary.

Thanks

- John

[Kristoff2]

murphyfields,

In the case you described the smallest circle would be the unit circle.  You could just included a test that checks if the smallest circle is outside the unit circle and if it is use the unit circle as the smallest circle.  There may be cases where this doesn't work so please include some more examples (and drawings) if you can.

Regards,

Sam K

Applications Engineer

National Instruments

[murphyfields]

Here is an example which shows the data which is contained in the unit circle, the unit circle, and the minimum enclosing circle which falls out of the allowed bounds.

[murphyfields]

OOPS, lets try this again

[NimbleThink]

Saw this post and it sounded interesting, however the EH algorithm just seemed too inefficient.

A quick search uncovers

http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

which discusses that the EH algorithm executes in O(n^2) whereas Megiddo discovered an algorithm which executes in O(n).

Regards and farewell,

Leif Kirschenbaum

(soon to be ex-test engineer and new reliability engineer)

[Brad]

Very helpful algorithm...thanks for posting! Any chance someone has an Inscribed circle algorithm (i.e. the maximum circle within an array of points that doesn't include any points)? I realize this is a much harder problem and I've seen some promising papers on how to do it using Convex Hull and Voronoi Diagrams, but before I try from scratch in LabVIEW, I thought I'd see if someone has already done it.

http://web.cs.swarthmore.edu/~adanner/cs97/s08/papers/schuster.pdf

I also saw the post here:

http://forums.ni.com/t5/LabVIEW/Roundness-calculations/td-p/917930/page/3

but I was getting error -20071 about "Analysis:  The input matrix is not positive definite." for some data sets, so I wanted to see if there was something more robust out there.

Thanks,

Brad

[toybag2]

Thanks perfect