Smallest circle around N points

[Darin.K]

Jeff, Isn't it always the special cases that get you?  I agree that the check for acuteness is a likely culprit for the (very occasional) hangs, along with the check for enclosure.  (Any time you are comparing floats it is a potential problem).  Unless a more interesting problem arises today (doubtful) I'll try to think about it during a break today.  Some documentation is also in order, I was in the wiring zone yesterday.  You can see the progression of my icons from nice picture, to simple picture, to words, to nothing.

RWiersma, Along with dusting off some interesting trig, you have stumbled upon a valuable lesson.  If you are doing a simple task in LV (like finding Max/Min of an array), and think "there must be an easier way," there probably is.

[Darin.K]

I have added a few comments, most details still found in the links.  I decided to use the law of cosines instead of the law of sines to determine acuteness.  Purring like a kitten so far.

[RWiersma]

I've been investigating this since I came back from lunch... for debugging: in the TestMinCircle.vi I drew a While loop. I placed an indicator on the i>32000 in the MinCircle.vi, mapped it out of the VI, and wired it to the loop in TestMinCircle. Failures are captured easily, and I constructed constants to feed the same data set on subsequent runs. The code will fail on the same data set, repeatably.

v2 is showing the same symptom.

Set the N points to something more tangible, (I've been using 4).

When in error condition, the state machine is showing state 2, 3, 4, 3, 2, 3, 4, 3, 2, 3, 4, 3, 2...etc

Can you provide your base formula for the CircumscribedCircle.vi? I might try to reconstruct that with a formula node.

RW

[Darin.K]

Always a chance for errors here.

D=2(x1(y2-y3)+x2(y3-y1)+x3(y1-y2))

xc = ((x1^2+y1^2)(y2-y3)+(x2^2+y2^2)(y3-y1)+(x3^2+y3^2)(y1-y2))/D

yc = ((x1^2+y1^2)(x3-x2)+(x2^2+y2^2)(x1-x3)+(x3^2+y3^2)(x2-x1))/D 

Be sure to turn the ^ into ** for the FN and you have to add explicit multiplications.

[RWiersma]

FN added; no joy.

I included the v3 LLB. Mods: FN module, and afore-mentioned debug options.

RW

Message Edited by RWiersma on 02-02-2010 02:04 PM

[RWiersma]

Fairly certain I've narrowed down the glitch to NewPoint.vi.

I installed a boolean functional global to feed the If/Then case, and the MinCircle.vi -never- crashes any longer.

I figured the FG was safe, since we still need to validate the data set before we give a successful exit. Worst case, we fail, come back around in 3 more cycles and we'll pass.  Ugly and inefficient, but it worked.

Working or not, it feels wrong, so I'll look into it tomorrow to find the problem.

 

I also am graphing the rotation. It appears there is a bug here, the rotation doesn't center about 0, it seems to center about (xc,yc).

[Darin.K]

You've spotted it.  The error lies in the picture you posted.  The Atan2 function should be fed from the translated x and y arrays (ie. after the subtraction of xc and yc).  I'll post fixed versions after some testing, but I'll bet it works if you connect the proper subtracted array to the index array functions that feed the Atan2.  Just make sure you get x to x and y to y.

[Darin.K · Accepted solution]

Third time is a charm, just goes to show that these things never work the first time (at least for me).  This ran 40 million times without problems.  I also added the option to preselect the furthest two points before starting.  Shouldn't be necessary most times.

[RWiersma]

Darin,

Your v3 is good.

We verified 10 samples to CAD, and I cycled several million sets of data through it. Can't beat it.

Thank you for your hardwork. Your dedication to this community is greatly appreciated.

-RW

[Darin.K]

Your welcome.  If you ask an interesting question (I am a sucker for math) participate in the development/debugging you'll find people around here ready to sweat their skulls off.

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.