## Weekend Programming Challenge Issue-9 Solutions

We got 7 solutions for the Issue-9 challenge:

• 3 C
• 2 Java
• 1 C#
• 1 Python

I’m surprised that we didn’t got more solutions as this challenge was pretty simple. Maybe the picture I put on the Challenge confused you?

What you have to do is to pick random (or first) three points and calc the radius and centre coordinates of the circle which pass through them (3 points always define circle).

Then to check rest of the point if belong to same circle which is trivial using Pythagorean theorem.

1. I wanted to do this, and knew exactly how to approach it (a matrix-based solution of the coefficients of the equation for the circle based on 3 points and then a check of the remaining points), but lack of time meant I never even opened my text editor… Shame really, as this is the kind of problem that Matlab/Octave were created for!

2. As someone not directly involved with the weekend challenges but who had to solve that exact problem not long ago because of a real-world CNC software bug (fiinding the centre of the circle going through 2 points), I can tell you that the problem is a seriously non-obvious one; furthermore I couldn’t find a single decent description of how to solve it on the net (but plenty of poorly or not at all answered questions about how it could be solved). Simply putting together the right equations will get you nowhere (they cannot be solved directly “for X”), the only thing that finally worked for me was re-learning the whole math of coordinate system roto-translations. Frankly, I’m not surprised at all…

3. Great Chappenge 😉 Interesting that we all went for much the same solution.

An alternative would be to simply return True if given three points, and use http://mathworld.wolfram.com/PtolemysTheorem.html for four (or more, keeping A, B and C fixed).

Iff the points are distributed roughly evenly around the (possible) circle, each point could be assigned a weight of 1, the centre C taken as the weighted average of all the points, and the variance of the distance from the points to C, and an iterative process could alternately perturb C in the plane such that the variance per radius decreases (increasing weights for points on the side of the circle where there are fewer). That sentence was already far too long; the other half of the iteration is to decrease the weight (potentially to zero) of outliers.

Nice to see that everybody used an epsilon 😉

• notzed
May 21, 2013 @ 03:32:32

Or use a hough transform?

epsilon – i guess we all know the reality of the pain of floating point.

4. Maybe it was too simple ?

5. notzed
May 21, 2013 @ 03:30:26

Maybe it just wasn’t interesting enough? 😉

I’m quite surprised there was no octave or 4gl solutions.