Click here to Skip to main content
13,139,773 members (51,485 online)
Rate this:
 
Please Sign up or sign in to vote.
See more:
Today's challenge is a simple one: given an arbitrary set of points in the x,y plane, determine the centre and radius of the smallest circle that will enclose all points. The circle may intersect points in the set.

Bonus points awarded for the use of an interesting language. Or an interesting use of a language.

What I have tried:

To take some time off.

Last challenge[^]'s winner was Jon McKee, but only if he promises never to do that again. Jon: email Sean your contact details and something appropriate will be sent in return.
Posted 5-Jan-17 15:36pm
Updated 12-Jan-17 2:26am
v2
Comments
Jon McKee 6-Jan-17 0:07am
   
"Bonus points awarded for use of an interesting language." "only if he promises never to do that again." :( Ok... :P
Rajesh R Subramanian 6-Jan-17 5:08am
   
Mr Maunder, could you please fix the formatting in my solution post? :(
Ralf Meier 6-Jan-17 8:10am
   
You could do it by yourself.
Use the function "Improve Solution" and you are able to change what you have written ...
Rajesh R Subramanian 6-Jan-17 19:06pm
   
Ah, thank you. It's been so long since I've posted in the Q/A forums that I'd actually forgotten this. :laugh:
0x01AA 6-Jan-17 12:13pm
   
"Or an interesting use of a language": What do you think about Schwizerdütsch? Swiss German - Wikipedia[^]
PIEBALDconsult 6-Jan-17 15:31pm
   
Got sample data and test results?
Jon McKee 6-Jan-17 23:56pm
   
I think that's up to us this time around.
PIEBALDconsult 8-Jan-17 16:42pm
   
Alas.
Graeme_Grant 7-Jan-17 9:05am
   
I posted an excel spreadsheet where you can place points and visualize the results. Will that help you? ;)
ppolymorphe 10-Jan-17 19:13pm
   
Looks like official sample datasets would be a good idea to avoid wrong solutions.
Graeme_Grant 10-Jan-17 20:15pm
   
Tey can use this spreadsheet[^] to [manually] enter points & results and see they pass.
ppolymorphe 10-Jan-17 20:42pm
   
Yes, I know, but they don't.
See Solution 12
you already seen it.
Graeme_Grant 10-Jan-17 20:57pm
   
I did see and commented. I shared the [manual] spreadsheet (with visual aid) as it appears they don't have a way of checking the results.
Kornfeld Eliyahu Peter 11-Jan-17 9:33am
   
It is acceptable to post an article as answer? I just made a lot of images and mathematical explanations I would like to share...
Chris Maunder 11-Jan-17 16:25pm
   
Absolutely
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 7

Solution 5 was my first attempt at this problem and the test points (more than posted) used reflected that the solution worked. So I converted to several different languages, partially as a learning curve and a challenge for myself.

Happy with my efforts above I shared the code and spreadsheet with my son, and as a typical client, was able to find a flaw in the formula used. So over lunch, I sat down with my university son and we explored the math and found that the problem is more complex than it initially appeared.

Solution below - my son's math problem solving and my coding - team effort. The solution that we used, was to: find the outer max points, remove the inner points (not required), then find the best fit with the remaining points.

I have included 7 tests - the first 3 go from simple to complex. The 4th test is a circle. So the radius and center supplied to calculate the points for the test should equal the calculated values. All 4 tests pass with 2 or more points on the smallest circle result. The check routine is rounded to 4 decimal places but doesn't have an extra margin of error for floating point math but appears to do the job.

Update: added VB.Net & Powershell versions

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace SmallestCircle
{
    class Program
    {
        static void Main(string[] args)
        {
            var tests = new List<Tuple<string, List<Tuple<float, float>>>>()
            {
                new Tuple<string, List<Tuple<float, float>>>("Triangle", Test1()),
                new Tuple<string, List<Tuple<float, float>>>("Box", Test2()),
                new Tuple<string, List<Tuple<float, float>>>("Cluster", Test3()),
                new Tuple<string, List<Tuple<float, float>>>("Spread", Test4()),
                new Tuple<string, List<Tuple<float, float>>>("Circle", Test5()),
                new Tuple<string, List<Tuple<float, float>>>("Ellispe", Test6()),
                new Tuple<string, List<Tuple<float, float>>>("Random", Test7())
            };
 
            for (int i = 0; i < tests.Count; i++)
            {
                var points = tests[i].Item2;
 
                Console.WriteLine("--------------------------------------------------------");
                Console.WriteLine($"** TEST: {i + 1} > {tests[i].Item1} - {points.Count} locations ....\r\n");
                if (points.Count > 50) Console.WriteLine("... this may take a little while...");
 
                var circle = SmallestCircle(points);
                var circlePos = new Func<Tuple<float, float>, string>((pt) =>
                {
                    float cpt = (float)Math.Round(Math.Pow(pt.Item1 - circle.Item2.Item1, 2) + Math.Pow(pt.Item2 - circle.Item2.Item2, 2), 4);
                    float crd = (float)Math.Round(Math.Pow(circle.Item1, 2), 4);
                    return cpt < crd ? "inside" : cpt == crd ? "on" : "outside";
                });
 
                Console.WriteLine($"RADIUS: {circle.Item1}  Center: ({circle.Item2.Item1},{circle.Item2.Item2})\r\n");
 
                foreach (var pt in points)
                    Console.WriteLine($"({pt.Item1},{pt.Item2}) is {circlePos(pt)} the circle");
            }
            Console.WriteLine("\r\n--------------------------------------------------------");
            Console.WriteLine($"{tests.Count} Test run. Scroll up to see results.");
            Console.WriteLine("\r\n-- Press any key to exit --");
            Console.ReadKey();
        }
 
        private static Tuple<float, Tuple<float, float>> SmallestCircle(List<Tuple<float, float>> points)
        {
            var angVal = new Func<Tuple<float, float>, Tuple<float, float>, float>((t1, t2) =>
            {
                float dx = t2.Item1 - t1.Item1, ax = Math.Abs(dx),
                        dy = t2.Item2 - t1.Item2, ay = Math.Abs(dy),
                        t = ax + ay == 0 ? 40f : dy / (ax + ay);
                if (dx < 0) t = 2 - t; else if (dy < 0) t = 4 + t;
                return t * 90;
            });
 
            var enclosesPts = new Func<Tuple<float, float>, float, IEnumerable<Tuple<float, float>>, bool>
                ((tc, tr, xpts) =>
                {
                    foreach (var pt in xpts)
                        if (Math.Pow(tc.Item1 - pt.Item1, 2) + Math.Pow(tc.Item2 - pt.Item2, 2) > tr)
                            return false;
                    return true;
                });
 
            var intersection = new Func<List<Tuple<Tuple<float, float>, Tuple<float, float>>>, Tuple<float, float>>((spts) =>
            {
                var da = new Tuple<float, float>(spts[0].Item2.Item1 - spts[0].Item1.Item1, spts[0].Item2.Item2 - spts[0].Item1.Item2);
                var db = new Tuple<float, float>(spts[1].Item2.Item1 - spts[1].Item1.Item1, spts[1].Item2.Item2 - spts[1].Item1.Item2);
                var d = (da.Item2 * db.Item1 - da.Item1 * db.Item2);
                if (d == 0) return new Tuple<float, float>(float.NaN, float.NaN); // nope...
                float e = ((spts[0].Item1.Item1 - spts[1].Item1.Item1) * db.Item2 + (spts[1].Item1.Item2 - spts[0].Item1.Item2) * db.Item1) / d;
                return new Tuple<float, float>(spts[0].Item1.Item1 + da.Item1 * e, spts[0].Item1.Item2 + da.Item2 * e);
            });
 
            var findCircle = new Func<List<Tuple<float, float>>, Tuple<float, Tuple<float, float>>>((triple) =>
            {
                var p1 = new Tuple<float, float>((triple[1].Item1 + triple[0].Item1) / 2, (triple[1].Item2 + triple[0].Item2) / 2);
                var d1 = new Tuple<float, float>(-(triple[1].Item2 - triple[0].Item2), triple[1].Item1 - triple[0].Item1);
                var p2 = new Tuple<float, float>((triple[2].Item1 + triple[1].Item1) / 2, (triple[2].Item2 + triple[1].Item2) / 2);
                var d2 = new Tuple<float, float>(-(triple[2].Item2 - triple[1].Item2), triple[2].Item1 - triple[1].Item1);
                var fc = intersection(new List<Tuple<Tuple<float, float>, Tuple<float, float>>>()
                {
                    new Tuple<Tuple<float, float>, Tuple<float, float>>(p1, new Tuple<float, float>(p1.Item1 + d1.Item1, p1.Item2 + d1.Item2)),
                    new Tuple<Tuple<float, float>, Tuple<float, float>>(p2, new Tuple<float, float>(p2.Item1 + d2.Item1, p2.Item2 + d2.Item2))
                });
                return new Tuple<float, Tuple<float, float>>((float)Math.Pow(fc.Item1 - triple[0].Item1, 2) + (float)Math.Pow(fc.Item2 - triple[0].Item2, 2), fc);
            });
 
            // calc outer points (trapezoid)
            Tuple<float, float> ul = points[0], ur = ul, bl = ul, br = ul;
            points.ForEach(pt =>
            {
                br = -pt.Item1 - pt.Item2 > -br.Item1 - br.Item2 ? br : pt;
                bl = pt.Item1 - pt.Item2 > bl.Item1 - bl.Item2 ? bl : pt;
                ur = -pt.Item1 + pt.Item2 > -ur.Item1 + ur.Item2 ? ur : pt;
                ul = pt.Item1 + pt.Item2 > ul.Item1 + ul.Item2 ? ul : pt;
            });
 
            // inner box
            var xmin = ul.Item1;
            var ymin = ul.Item2;
 
            var xmax = ur.Item1;
            if (ymin < ur.Item2) ymin = ur.Item2;
 
            if (xmax > br.Item1) xmax = br.Item1;
            var ymax = br.Item2;
 
            if (xmin < bl.Item1) xmin = bl.Item1;
            if (ymax > bl.Item2) ymax = bl.Item2;
 
            // remove inner unwanted points
            var pts = points.Where(pt => pt.Item1 <= xmin || pt.Item1 >= xmax || pt.Item2 <= ymin || pt.Item2 >= ymax).ToList();
 
            // find point with smallest y value (and x value if tie) & add to pts
            Tuple<float, float> minPt = null;
            points.ForEach(pt => minPt = (minPt == null) || (pt.Item2 < minPt.Item2 || ((pt.Item2 == minPt.Item2) && (pt.Item1 < minPt.Item1))) ? pt : minPt);
            // Find outer points to find smallest circle
            var region = new List<Tuple<float, float>>() { minPt };
            pts.Remove(minPt);
 
            float ang1 = 0;
            while (true)
            {
                if (pts.Count == 0) break;
 
                var pt = region[region.Count - 1];
                minPt = points[0];
                float ang2 = 3600;
 
                points.ForEach(p =>
                {
                    var t = angVal(pt, p);
                    if (t >= ang1 && ang2 > t)
                    {
                        ang2 = t;
                        minPt = p;
                    }
                });
 
                var ang = angVal(pt, region[0]);
                if (ang >= ang1 && ang2 >= ang) break;
 
                region.Add(minPt);
                pts.Remove(minPt);
                ang1 = ang2;
            }
 
            // now fit smallest circle
            var radius = float.MaxValue;
            var center = region[0];
 
            // first try for float points on circle
            for (int i = 0; i < region.Count; i++)
            {
                var pt1 = region[i];
                region.Skip(i + 1).ToList().ForEach(pt2 =>
                {
                    var tc = new Tuple<float, float>((pt1.Item1 + pt2.Item1) / 2f, (pt1.Item2 + pt2.Item2) / 2f);
                    var dtc = new Tuple<float, float>(tc.Item1 - pt1.Item1, tc.Item2 - pt1.Item2);
                    var tr = (float)Math.Pow(dtc.Item1, 2) + (float)Math.Pow(dtc.Item2, 2);
                    if (tr < radius)
                        if (enclosesPts(tc, tr, region.Except(new List<Tuple<float, float>>() { pt1, pt2 })))
                        {
                            center = tc;
                            radius = tr;
                        }
                });
            }
 
            // Second pass
            for (int i = 0; i < region.Count; i++)
            {
                var pt1 = region[i];
                for (int j = i + 1; j < region.Count - i - 1; j++)
                {
                    var pt2 = region[j];
                    region.Skip(j + 1).ToList().ForEach(pt3 =>
                    {
                        var fc = findCircle(new List<Tuple<float, float>>() { pt1, pt2, pt3 });
                        if (fc.Item1 < radius)
                        {
                            if (enclosesPts(fc.Item2, fc.Item1, region.Except(new List<Tuple<float, float>>() { pt1, pt2, pt3 })))
                            {
                                center = fc.Item2;
                                radius = fc.Item1;
                            }
                        }
                    });
                }
            }
 
            return new Tuple<float, Tuple<float, float>>((radius == float.MaxValue) ? 0 : (float)Math.Sqrt(radius), center);
        }
 
        // simple triangle
        private static List<Tuple<float, float>> Test1()
        {
            return new List<Tuple<float, float>>()
        {
            new Tuple<float, float>(0.5f, 0.75f),
            new Tuple<float, float>(8.5f, 1.63f),
            new Tuple<float, float>(4.87f,6.75f)
        };
        }
 
        // simple box
        private static List<Tuple<float, float>> Test2()
        {
            return new List<Tuple<float, float>>()
        {
            new Tuple<float, float>(0,0),
            new Tuple<float, float>(0,5),
            new Tuple<float, float>(5,5),
            new Tuple<float, float>(5,0),
        };
        }
 
        // cluster
        private static List<Tuple<float, float>> Test3()
        {
            return new List<Tuple<float, float>>()
            {
                new Tuple<float, float>(0.5f, 0.75f),
                new Tuple<float, float>(1.25f, 0.85f),
                new Tuple<float, float>(3.86f, 2.19f),
                new Tuple<float, float>(2.11f, 4.65f),
                new Tuple<float, float>(1.17f, 2.01f),
                new Tuple<float, float>(3.19f, 1.63f),
                new Tuple<float, float>(4.87f, 5.39f)
            };
        }
 
        // spread
        private static List<Tuple<float, float>> Test4()
        {
            return new List<Tuple<float, float>>()
            {
                new Tuple<float, float>(0.5f, 0.75f),
                new Tuple<float, float>(1.25f, 0.85f),
                new Tuple<float, float>(3.86f, 2.19f),
                new Tuple<float, float>(11f, 7f),
                new Tuple<float, float>(1.17f, 2.01f),
                new Tuple<float, float>(15f, 1.63f),
                new Tuple<float, float>(4.87f,10f)
            };
        }
 
        // Point on circle
        private static List<Tuple<float, float>> Test5()
        {
            int step = 10; // 1 to 360
            float r = 3.187f, x = 2.685f, y = 3.07f; // radius, center x/y
            float rad = (float)Math.PI / 180;
            var points = new List<Tuple<float, float>>();
 
            for (int i = 0; i < 360; i += step)
                points.Add(new Tuple<float, float>((float)(r * Math.Cos(i * rad) + x), (float)(r * Math.Sin(i * rad) + y)));
 
            return points;
        }
    
        // Point on an ellipse
        private static List<Tuple<float, float>> Test6()
        {
            int step = 1, count = 0; 
            var points = new List<Tuple<float, float>>();
 
            // rectangle 10 x 6 =  2, 2, 10, 6 < x, y, width, height
            float rx = 2f, ry = 2f, rw = 10f, rh = 6f,
                    Dx = rx + 10 / 2, Dy = ry + 6 / 2, Rx = rw / 2, Ry = rh / 2,
                    A = 1f / Rx / Rx, B = 1f / Ry / Ry, C = 0f, D = -2f * Dx / Rx / Rx, E = -2f * Dy / Ry / Ry, F = Dx * Dx / Rx / Rx + Dy / Ry / Ry - 1;
 
            for (float x = Dx - Rx; x <= Dx + Rx; x++)
            {
                float r = (x - Dx) / Rx;
                r = 1 - r * r;
                if (r >= 0f && count % step == 0)
                    points.Add(new Tuple<float, float>(x, (float)(Dy + Ry * Math.Sqrt(r))));
                count++;
            }
            for (float x = Dx + Rx; x >= Dx - Rx; x--)
            {
                float r = (x - Dx) / Rx;
                r = 1 - r * r;
                if (r > 0f && count % step == 0)
                    points.Add(new Tuple<float, float>(x, (float)(Dy - Ry * Math.Sqrt(r))));
                count++;
            }
 
            return points;
        }
 
        // Random
        private static List<Tuple<float, float>> Test7()
        {
            var randomFloat = new Func<float, float, float>((min, max) =>
            {
                double range = (double)max - (double)min;
                double sample = random.NextDouble();
                double scaled = (sample * range);
                return (float)scaled;
            });
 
            var nextRandom = new Func<float>(() => (float)Math.Round(randomFloat(-10f, 10f),2));
            var count = random.Next(2, 20);
 
            var points = new List<Tuple<float, float>>();
 
            for (int i = 0; i < count; i++)
                points.Add(new Tuple<float, float>(nextRandom(), nextRandom()));
 
            return points;
        }
        static Random random = new Random();
    }
}

** Update #2: VB.NET version
Module Module1
    Sub Main()
 
        Dim tests = New List(Of Tuple(Of String, List(Of Tuple(Of Single, Single))))() From {
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Triangle", Test1()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Box", Test2()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Cluster", Test3()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Spread", Test4()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Circle", Test5()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Ellispe", Test6()),
                    New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Random", Test7())
        }
 
        For i As Integer = 0 To tests.Count - 1
            Dim points = tests(i).Item2
 
            Console.WriteLine("--------------------------------------------------------")
            Console.WriteLine($"** TEST: {i + 1} > {tests(i).Item1} - {points.Count} locations ...." & vbCr & vbLf)
            If points.Count > 50 Then
                Console.WriteLine("... this may take a little while...")
            End If
 
            Dim circle = SmallestCircle(points)
            Dim circlePos = New Func(Of Tuple(Of Single, Single), String)(
                Function(pt)
                    Dim cpt As Single = CSng(Math.Round(Math.Pow(pt.Item1 - circle.Item2.Item1, 2) + Math.Pow(pt.Item2 - circle.Item2.Item2, 2), 4))
                    Dim crd As Single = CSng(Math.Round(Math.Pow(circle.Item1, 2), 4))
                    Return If(cpt < crd, "inside", If(cpt = crd, "on", "outside"))
 
                End Function)
 
            Console.WriteLine($"RADIUS: {circle.Item1}  Center: ({circle.Item2.Item1},{circle.Item2.Item2})" & vbCr & vbLf)
 
            For Each pt In points
                Console.WriteLine($"({pt.Item1},{pt.Item2}) is {circlePos(pt)} the circle")
            Next
        Next
        Console.WriteLine(vbCr & vbLf & "--------------------------------------------------------")
        Console.WriteLine($"{tests.Count} Test run. Scroll up to see results.")
        Console.WriteLine(vbCr & vbLf & "-- Press any key to exit --")
        Console.ReadKey()
 
    End Sub
 
    Function SmallestCircle(points As List(Of Tuple(Of Single, Single))) As Tuple(Of Single, Tuple(Of Single, Single))
 
        Dim angVal = New Func(Of Tuple(Of Single, Single), Tuple(Of Single, Single), Single) _
            (Function(t1, t2)
                 Dim dx As Single = t2.Item1 - t1.Item1, ax As Single = Math.Abs(dx),
                     dy As Single = t2.Item2 - t1.Item2, ay As Single = Math.Abs(dy),
                     t As Single = If(ax + ay = 0, 40.0F, dy / (ax + ay))
                 If dx < 0 Then
                     t = 2 - t
                 ElseIf dy < 0 Then
                     t = 4 + t
                 End If
                 Return t * 90
 
             End Function)
 
        Dim enclosesPts = New Func(Of Tuple(Of Single, Single), Single, IEnumerable(Of Tuple(Of Single, Single)), Boolean) _
            (Function(tc, tr, xpts)
                 For Each pt In xpts
                     If Math.Pow(tc.Item1 - pt.Item1, 2) + Math.Pow(tc.Item2 - pt.Item2, 2) > tr Then
                         Return False
                     End If
                 Next
                 Return True
 
             End Function)
 
        Dim intersection = New Func(Of List(Of Tuple(Of Tuple(Of Single, Single), Tuple(Of Single, Single))), Tuple(Of Single, Single)) _
            (Function(spts)
                 Dim da = New Tuple(Of Single, Single)(spts(0).Item2.Item1 - spts(0).Item1.Item1, spts(0).Item2.Item2 - spts(0).Item1.Item2)
                 Dim db = New Tuple(Of Single, Single)(spts(1).Item2.Item1 - spts(1).Item1.Item1, spts(1).Item2.Item2 - spts(1).Item1.Item2)
                 Dim d = (da.Item2 * db.Item1 - da.Item1 * db.Item2)
                 If d = 0 Then
                     Return New Tuple(Of Single, Single)(Single.NaN, Single.NaN)
                 End If
                 ' nope...
                 Dim e As Single = ((spts(0).Item1.Item1 - spts(1).Item1.Item1) * db.Item2 + (spts(1).Item1.Item2 - spts(0).Item1.Item2) * db.Item1) / d
                 Return New Tuple(Of Single, Single)(spts(0).Item1.Item1 + da.Item1 * e, spts(0).Item1.Item2 + da.Item2 * e)
 
             End Function)
 
        Dim findCircle = New Func(Of List(Of Tuple(Of Single, Single)), Tuple(Of Single, Tuple(Of Single, Single))) _
            (Function(triple)
                 Dim p1 = New Tuple(Of Single, Single)((triple(1).Item1 + triple(0).Item1) / 2, (triple(1).Item2 + triple(0).Item2) / 2)
                 Dim d1 = New Tuple(Of Single, Single)(-(triple(1).Item2 - triple(0).Item2), triple(1).Item1 - triple(0).Item1)
                 Dim p2 = New Tuple(Of Single, Single)((triple(2).Item1 + triple(1).Item1) / 2, (triple(2).Item2 + triple(1).Item2) / 2)
                 Dim d2 = New Tuple(Of Single, Single)(-(triple(2).Item2 - triple(1).Item2), triple(2).Item1 - triple(1).Item1)
                 Dim fc = intersection(New List(Of Tuple(Of Tuple(Of Single, Single), Tuple(Of Single, Single)))() _
                    From {
                        New Tuple(Of Tuple(Of Single, Single), Tuple(Of Single, Single))(p1, New Tuple(Of Single, Single)(p1.Item1 + d1.Item1, p1.Item2 + d1.Item2)),
                        New Tuple(Of Tuple(Of Single, Single), Tuple(Of Single, Single))(p2, New Tuple(Of Single, Single)(p2.Item1 + d2.Item1, p2.Item2 + d2.Item2))
                    })
                 Return New Tuple(Of Single, Tuple(Of Single, Single))(CSng(Math.Pow(fc.Item1 - triple(0).Item1, 2)) + CSng(Math.Pow(fc.Item2 - triple(0).Item2, 2)), fc)
 
             End Function)
 
        ' calc outer points (trapezoid)
        Dim ul As Tuple(Of Single, Single) = points(0),
            ur As Tuple(Of Single, Single) = ul,
            bl As Tuple(Of Single, Single) = ul,
            br As Tuple(Of Single, Single) = ul
        points.ForEach(
            Sub(pt)
                br = If(-pt.Item1 - pt.Item2 > -br.Item1 - br.Item2, br, pt)
                bl = If(pt.Item1 - pt.Item2 > bl.Item1 - bl.Item2, bl, pt)
                ur = If(-pt.Item1 + pt.Item2 > -ur.Item1 + ur.Item2, ur, pt)
                ul = If(pt.Item1 + pt.Item2 > ul.Item1 + ul.Item2, ul, pt)
            End Sub)
 
        ' inner box
        Dim xmin = ul.Item1
        Dim ymin = ul.Item2
 
        Dim xmax = ur.Item1
        If ymin < ur.Item2 Then
            ymin = ur.Item2
        End If
 
        If xmax > br.Item1 Then
            xmax = br.Item1
        End If
        Dim ymax = br.Item2
 
        If xmin < bl.Item1 Then
            xmin = bl.Item1
        End If
        If ymax > bl.Item2 Then
            ymax = bl.Item2
        End If
 
        ' remove inner unwanted points
        Dim pts = points.Where(Function(pt) _
            pt.Item1 <= xmin OrElse pt.Item1 >= xmax OrElse pt.Item2 <= ymin OrElse pt.Item2 >= ymax).ToList()
 
        ' find point with smallest y value (and x value if tie) & add to pts
        Dim minPt As Tuple(Of Single, Single) = Nothing
        points.ForEach(Function(pt) InlineAssignHelper(minPt, If((minPt Is Nothing) OrElse (pt.Item2 < minPt.Item2 OrElse ((pt.Item2 = minPt.Item2) AndAlso (pt.Item1 < minPt.Item1))), pt, minPt)))
        ' Find outer points to find smallest circle
        Dim region = New List(Of Tuple(Of Single, Single))() From {minPt}
        pts.Remove(minPt)
 
        Dim ang1 As Single = 0
        While True
            If pts.Count = 0 Then
                Exit While
            End If
 
            Dim pt = region(region.Count - 1)
            minPt = points(0)
            Dim ang2 As Single = 3600
 
            points.ForEach(Sub(p)
                               Dim t = angVal(pt, p)
                               If t >= ang1 AndAlso ang2 > t Then
                                   ang2 = t
                                   minPt = p
                               End If
                           End Sub)
 
            Dim ang = angVal(pt, region(0))
            If ang >= ang1 AndAlso ang2 >= ang Then
                Exit While
            End If
 
            region.Add(minPt)
            pts.Remove(minPt)
            ang1 = ang2
        End While
 
        ' now fit smallest circle
        Dim radius = Single.MaxValue
        Dim center = region(0)
 
        ' first try for float points on circle
        For i As Integer = 0 To region.Count - 1
            Dim pt1 = region(i)
            region.Skip(i + 1).ToList().ForEach(
                Sub(pt2)
                    Dim tc = New Tuple(Of Single, Single)((pt1.Item1 + pt2.Item1) / 2.0F, (pt1.Item2 + pt2.Item2) / 2.0F)
                    Dim dtc = New Tuple(Of Single, Single)(tc.Item1 - pt1.Item1, tc.Item2 - pt1.Item2)
                    Dim tr = CSng(Math.Pow(dtc.Item1, 2)) + CSng(Math.Pow(dtc.Item2, 2))
                    If tr < radius Then
                        If enclosesPts(tc, tr, region.Except(New List(Of Tuple(Of Single, Single))() From {pt1, pt2})) Then
                            center = tc
                            radius = tr
                        End If
                    End If
                End Sub)
        Next
 
        ' Second pass
        For i As Integer = 0 To region.Count - 1
            Dim pt1 = region(i)
            For j As Integer = i + 1 To region.Count - i - 2
                Dim pt2 = region(j)
                region.Skip(j + 1).ToList().ForEach(
                    Sub(pt3)
                        Dim fc = findCircle(New List(Of Tuple(Of Single, Single))() From {pt1, pt2, pt3})
                        If fc.Item1 < radius Then
                            If enclosesPts(fc.Item2, fc.Item1, region.Except(New List(Of Tuple(Of Single, Single))() From {pt1, pt2, pt3})) Then
                                center = fc.Item2
                                radius = fc.Item1
                            End If
                        End If
                    End Sub)
            Next
        Next
 
        Return New Tuple(Of Single, Tuple(Of Single, Single))(If((radius = Single.MaxValue), 0, CSng(Math.Sqrt(radius))), center)
    End Function
 
    ' simple triangle
    Function Test1() As List(Of Tuple(Of Single, Single))
        Return New List(Of Tuple(Of Single, Single))() From {
            New Tuple(Of Single, Single)(0.5F, 0.75F),
            New Tuple(Of Single, Single)(8.5F, 1.63F),
            New Tuple(Of Single, Single)(4.87F, 6.75F)
        }
    End Function
 
    ' simple box
    Function Test2() As List(Of Tuple(Of Single, Single))
        Return New List(Of Tuple(Of Single, Single))() From {
            New Tuple(Of Single, Single)(0, 0),
            New Tuple(Of Single, Single)(0, 5),
            New Tuple(Of Single, Single)(5, 5),
            New Tuple(Of Single, Single)(5, 0)
        }
    End Function
 
    ' cluster
    Function Test3() As List(Of Tuple(Of Single, Single))
        Return New List(Of Tuple(Of Single, Single))() From {
            New Tuple(Of Single, Single)(0.5F, 0.75F),
            New Tuple(Of Single, Single)(1.25F, 0.85F),
            New Tuple(Of Single, Single)(3.86F, 2.19F),
            New Tuple(Of Single, Single)(2.11F, 4.65F),
            New Tuple(Of Single, Single)(1.17F, 2.01F),
            New Tuple(Of Single, Single)(3.19F, 1.63F),
            New Tuple(Of Single, Single)(4.87F, 5.39F)
        }
    End Function
 
    ' spread
    Function Test4() As List(Of Tuple(Of Single, Single))
        Return New List(Of Tuple(Of Single, Single))() From {
            New Tuple(Of Single, Single)(0.5F, 0.75F),
            New Tuple(Of Single, Single)(1.25F, 0.85F),
            New Tuple(Of Single, Single)(3.86F, 2.19F),
            New Tuple(Of Single, Single)(11.0F, 7.0F),
            New Tuple(Of Single, Single)(1.17F, 2.01F),
            New Tuple(Of Single, Single)(15.0F, 1.63F),
            New Tuple(Of Single, Single)(4.87F, 10.0F)
        }
    End Function
 
    ' Point on circle
    Function Test5() As List(Of Tuple(Of Single, Single))
        Dim [step] As Integer = 10
        ' 1 to 360
        Dim r As Single = 3.187F, x As Single = 2.685F, y As Single = 3.07F
        ' radius, center x/y
        Dim rad As Single = CSng(Math.PI) / 180
        Dim points = New List(Of Tuple(Of Single, Single))()
 
        Dim i As Integer = 0
        While i < 360
            points.Add(New Tuple(Of Single, Single)(CSng(r * Math.Cos(i * rad) + x), CSng(r * Math.Sin(i * rad) + y)))
            i += [step]
        End While
 
        Return points
    End Function
 
    ' Point on an ellipse
    Function Test6() As List(Of Tuple(Of Single, Single))
        Dim [step] As Integer = 1, count As Integer = 0
        Dim points = New List(Of Tuple(Of Single, Single))()
 
        ' rectangle 10 x 6 =  2, 2, 10, 6 < x, y, width, height
        Dim rx As Single = 2.0F, ry2 As Single = 2.0F, rw As Single = 10.0F, rh As Single = 6.0F, Dx As Single = rx + 10 / 2, Dy As Single = ry2 + 6 / 2,
            Rx3 As Single = rw / 2, Ry4 As Single = rh / 2, A As Single = 1.0F / Rx3 / Rx3, B As Single = 1.0F / Ry4 / Ry4, C As Single = 0F,
            D As Single = -2.0F * Dx / Rx3 / Rx3, E As Single = -2.0F * Dy / Ry4 / Ry4, F As Single = Dx * Dx / Rx3 / Rx3 + Dy / Ry4 / Ry4 - 1
 
        For x As Single = Dx - Rx3 To Dx + Rx3
            Dim r As Single = (x - Dx) / Rx3
            r = 1 - r * r
            If r >= 0F AndAlso count Mod [step] = 0 Then
                points.Add(New Tuple(Of Single, Single)(x, CSng(Dy + Ry4 * Math.Sqrt(r))))
            End If
            count += 1
        Next
        For x As Single = Dx + Rx3 To Dx - Rx3 Step -1
            Dim r As Single = (x - Dx) / Rx3
            r = 1 - r * r
            If r > 0F AndAlso count Mod [step] = 0 Then
                points.Add(New Tuple(Of Single, Single)(x, CSng(Dy - Ry4 * Math.Sqrt(r))))
            End If
            count += 1
        Next
 
        Return points
    End Function
 
    ' Random
    Function Test7() As List(Of Tuple(Of Single, Single))
        Dim randomFloat = New Func(Of Single, Single, Single) _
            (Function(min, max)
                 Dim range As Double = CDbl(max) - CDbl(min)
                 Dim sample As Double = random.NextDouble()
                 Dim scaled As Double = (sample * range)
                 Return CSng(scaled)
             End Function)
 
        Dim nextRandom = New Func(Of Single)(Function() CSng(Math.Round(randomFloat(-10.0F, 10.0F), 2)))
        Dim count = random.[Next](2, 20)
 
        Dim points = New List(Of Tuple(Of Single, Single))()
 
        For i As Integer = 0 To count - 1
            points.Add(New Tuple(Of Single, Single)(nextRandom(), nextRandom()))
        Next
 
        Return points
 
    End Function
 
    Dim random As New Random()
 
    Function InlineAssignHelper(Of T)(ByRef target As T, value As T) As T
        target = value
        Return value
    End Function
 
End Module

Outputs:
--------------------------------------------------------
** TEST: 1 > Triangle - 3 locations ....
 
RADIUS: 4.245819  Center: (4.351951,2.535904)
 
(0.5,0.75) is on the circle
(8.5,1.63) is on the circle
(4.87,6.75) is on the circle
--------------------------------------------------------
** TEST: 2 > Box - 4 locations ....
 
RADIUS: 3.535534  Center: (2.5,2.5)
 
(0,0) is on the circle
(0,5) is on the circle
(5,5) is on the circle
(5,0) is on the circle
--------------------------------------------------------
** TEST: 3 > Cluster - 7 locations ....
 
RADIUS: 3.186946  Center: (2.685,3.07)
 
(0.5,0.75) is on the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(2.11,4.65) is inside the circle
(1.17,2.01) is inside the circle
(3.19,1.63) is inside the circle
(4.87,5.39) is on the circle
--------------------------------------------------------
** TEST: 4 > Spread - 7 locations ....
 
RADIUS: 7.49485  Center: (7.638026,3.03503)
 
(0.5,0.75) is on the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(11,7) is inside the circle
(1.17,2.01) is inside the circle
(15,1.63) is on the circle
(4.87,10) is on the circle
--------------------------------------------------------
** TEST: 5 > Circle - 36 locations ....
 
RADIUS: 3.187  Center: (2.685,3.07)
 
(5.872,3.07) is on the circle
(5.823582,3.623417) is on the circle
(5.679801,4.160018) is on the circle
(5.445023,4.6635) is on the circle
(5.126384,5.118564) is on the circle
(4.733564,5.511384) is on the circle
(4.2785,5.830023) is on the circle
(3.775018,6.0648) is on the circle
(3.238417,6.208582) is on the circle
(2.685,6.257) is on the circle
(2.131583,6.208582) is on the circle
(1.594982,6.0648) is on the circle
(1.0915,5.830023) is on the circle
(0.6364359,5.511384) is on the circle
(0.2436163,5.118564) is on the circle
(-0.07502302,4.6635) is on the circle
(-0.3098004,4.160018) is on the circle
(-0.4535824,3.623417) is on the circle
(-0.5020001,3.07) is on the circle
(-0.4535824,2.516583) is on the circle
(-0.3098005,1.979982) is on the circle
(-0.07502309,1.4765) is on the circle
(0.2436162,1.021436) is on the circle
(0.6364357,0.6286163) is on the circle
(1.0915,0.309977) is on the circle
(1.594982,0.07519955) is on the circle
(2.131583,-0.06858239) is on the circle
(2.685,-0.1170001) is on the circle
(3.238417,-0.06858243) is on the circle
(3.775018,0.07519948) is on the circle
(4.2785,0.3099769) is on the circle
(4.733564,0.6286162) is on the circle
(5.126383,1.021436) is on the circle
(5.445023,1.4765) is on the circle
(5.679801,1.979982) is on the circle
(5.823582,2.516583) is on the circle
--------------------------------------------------------
** TEST: 6 > Ellispe - 20 locations ....
 
RADIUS: 5  Center: (7,5)
 
(2,5) is on the circle
(3,6.8) is inside the circle
(4,7.4) is inside the circle
(5,7.749546) is inside the circle
(6,7.939388) is inside the circle
(7,8) is inside the circle
(8,7.939388) is inside the circle
(9,7.749546) is inside the circle
(10,7.4) is inside the circle
(11,6.8) is inside the circle
(12,5) is on the circle
(11,3.2) is inside the circle
(10,2.6) is inside the circle
(9,2.250455) is inside the circle
(8,2.060612) is inside the circle
(7,2) is inside the circle
(6,2.060612) is inside the circle
(5,2.250455) is inside the circle
(4,2.6) is inside the circle
(3,3.2) is inside the circle
--------------------------------------------------------
** TEST: 7 > Random - 10 locations ....
 
RADIUS: 10.04682  Center: (10.005,6.915)
 
(10.11,12.58) is inside the circle
(3.81,1.28) is inside the circle
(0.22,7.51) is inside the circle
(9.69,9.01) is inside the circle
(17.69,8.97) is inside the circle
(12.43,7.64) is inside the circle
(0.56,10.34) is on the circle
(19.45,3.49) is on the circle
(13.65,13.74) is inside the circle
(13.53,2.39) is inside the circle
 
--------------------------------------------------------
7 Test run. Scroll up to see results.
 
-- Press any key to exit --


I hope you all enjoy my tuple madness! :)

** Update #2: Powershell version
using namespace System.Collections.Generic;
 
function Main
{
    $tests = [System.Tuple]::Create("Triangle", (Test1)),
             [System.Tuple]::Create("Triangle", (Test2)),
             [System.Tuple]::Create("Cluster", (Test3)),
             [System.Tuple]::Create("Spread", (Test4)),
             [System.Tuple]::Create("Circle", (Test5)),
             [System.Tuple]::Create("Ellispe", (Test6)),
             [System.Tuple]::Create("Random", (Test7));
 
    for ($i = 0; $i -lt $tests.Count; $i++) {
        $points = $tests[$i].Item2;
        $id = $i + 1; $name = $tests[$i].Item1; $loc = $points.Count; $ran = $tests.Count;
        echo "--------------------------------------------------------";
        echo "** TEST: $id > $name - $loc locations ....`r`n";
        if ($points.Count -gt 50) { echo "... this may take a little while..."; }
 
        $circle = SmallestCircle($points);
        $r = $circle.Item1; $c = $circle.Item2;
        echo "RADIUS: $r  CENTER: $c`r`n";
 
        $points | foreach {
            $state = circlePos([System.Tuple]::Create($_, $circle));
            echo "$_ is $state the circle";
        }
    }
    echo "`r`n--------------------------------------------------------";
    echo "$ran Tests run. Scroll up to see results.";
}
 
function CirclePos($p)
{
    $pt = $p.Item1;
    $circle = $p.Item2;
    $cpt = [Math]::Round([Math]::Pow($pt.Item1 - $circle.Item2.Item1, 2) + [Math]::Pow($pt.Item2 - $circle.Item2.Item2, 2), 4);
    $crd = [Math]::Round([Math]::Pow($circle.Item1, 2), 4);
    $state = "outside";
    if ($cpt -lt $crd) { $state = "inside"; } elseif ($cpt -eq $crd) { $state = "on"; }
    return $state;
}
 

function AngVal($p)
{
    $dx = $p[1].Item1 - $p[0].Item1;
    $ax = [Math]::Abs($dx);
    $dy = $p[1].Item2 - $p[0].Item2;
    $ay = [Math]::Abs($dy);
    if (($ax + $ay) -eq 0) { $t = 40; } else { $t = $dy / ($ax + $ay); }
    if ($dx -lt 0) { $t = 2 - $t; } elseif ($dy -lt 0) { $t = 4 + $t; }
    return $t * 90;
}
 
function EnclosesPts($p)
{
    $tc = $p[0];
    $tr = $p[1];
    $xpts = {$p[2]}.Invoke();
    for ($i = 0; $i -lt $xpts.Count; $i++) {
        if ([Math]::Pow($tc.Item1 - $xpts[$i].Item1, 2) + [Math]::Pow($tc.Item2 - $xpts[$i].Item2, 2) -gt $tr) { 
            return $false; 
        } 
    }
    return $true;
}
 
function Intersection($p)
{
    $da = [System.Tuple]::Create(($p.Item1[1].Item1 - $p.Item1[0].Item1),($p.Item1[1].Item2 - $p.Item1[0].Item2));
    $db = [System.Tuple]::Create(($p.Item2[1].Item1 - $p.Item2[0].Item1),($p.Item2[1].Item2 - $p.Item2[0].Item2));
    $d = ($da.Item2 * $db.Item1 - $da.Item1 * $db.Item2);
    if ($d -eq 0) { return [System.Tuple]::Create(([float]::NaN), ([float]::NaN)); } # nope...
    $e = (($p.Item1[0].Item1 - $p.Item2[0].Item1) * $db.Item2 + ($p.Item2[0].Item2 - $p.Item1[0].Item2) * $db.Item1) / $d;
    return [System.Tuple]::Create(($p.Item1[0].Item1 + $da.Item1 * $e), ($p.Item1[0].Item2 + $da.Item2 * $e));
};
 
function FindCircle($p)
{
    $p1 = [System.Tuple]::Create((($p[1].Item1 + $p[0].Item1) / 2), (($p[1].Item2 + $p[0].Item2) / 2));
    $d1 = [System.Tuple]::Create((-($p[1].Item2 - $p[0].Item2)), ($p[1].Item1 - $p[0].Item1));
    $p2 = [System.Tuple]::Create((($p[2].Item1 + $p[1].Item1) / 2), (($p[2].Item2 + $p[1].Item2) / 2));
    $d2 = [System.Tuple]::Create((-($p[2].Item2 - $p[1].Item2)), ($p[2].Item1 - $p[1].Item1));
    $fc = Intersection([System.Tuple]::Create(
        ($p1, ([System.Tuple]::Create(($p1.Item1 + $d1.Item1), ($p1.Item2 + $d1.Item2)))), 
        ($p2, ([System.Tuple]::Create($p2.Item1 + $d2.Item1, $p2.Item2 + $d2.Item2)))));
    return [System.Tuple]::Create([Math]::Pow($fc.Item1 - $p[0].Item1, 2) + [Math]::Pow($fc.Item2 - $p[0].Item2, 2), $fc);
}
 
function SmallestCircle($points) 
{
    # trim unwanted output...
    return process($points) | Where-Object {$_ -ne $true -and $_ -ne $false};
}
 
function process($points) 
{ 
    $ul = $bl = $br = $points[0];
    $points | foreach{
        if(-$_.Item1 - $_.Item2 -lt -$br.Item1 - $br.Item2) { $br = $_; }
        if($_.Item1 - $_.Item2 -lt $bl.Item1 - $bl.Item2) { $bl = $_; }
        if(-$_.Item1 + $_.Item2 -lt -$ur.Item1 + $ur.Item2) { $ur = $_; }
        if($_.Item1 + $_.Item2 -lt $ul.Item1 + $ul.Item2) { $ul = $_; }
    };
 
    # inner box
    $xmin = $ul.Item1;
    $ymin = $ul.Item2;
 
    $xmax = $ur.Item1;
    if ($ymin -lt $ur.Item2) { $ymin = $ur.Item2; }
 
    if ($xmax -gt $br.Item1) { $xmax = $br.Item1; }
    $ymax = $br.Item2;
 
    if ($xmin -lt $bl.Item1) { $xmin = $bl.Item1; }
    if ($ymax -gt $bl.Item2) { $ymax = $bl.Item2; }
 
    # find point with smallest y value (and x value if tie) & add to pts
    $zpts = $points | foreach{ if ($_.Item1 -le $xmin -or $_.Item1 -ge $xmax -or $_.Item2 -le $ymin -or $_.Item2 -ge $ymax) { $_; } }
    $pts = {$zpts}.Invoke();
 
    $points | foreach { 
        if ($minPt -eq $null -or ($_.Item2 -lt $minPt.Item2 -or (($_.Item2 -eq $minPt.Item2) -and ($_.Item1 -lt $minPt.Item1)))) 
            { $minPt = $_; } 
    }
 
    # Find outer points to find smallest circle
    $region ={$minPt}.Invoke();
    $pts.Remove($minPt);
 
    $ang1 = 0;
    While ($true)
    {
        if ($pts.Count -eq 0) { break; }
 
        $pt = $region[$region.Count - 1];
        $minPt = $points[0];
        $ang2 = 3600;
 
        $points | foreach {
            $t = AngVal($pt, $_);
            if ($t -ge $ang1 -and $ang2 -gt $t) {
                $ang2 = $t;
                $minPt = $_;
            }
        }
 
        $ang = AngVal($pt, $region[0]);
        if ($ang -ge $ang1 -and $ang2 -ge $ang) { break; }
 
        $region.Add($minPt);
        $pts.Remove($minPt);
        $ang1 = $ang2;
   }
 
   # now fit smallest circle
   $radius = [float]::MaxValue;
   $center = $region[0];
 
   # first try for float points on circle
    for ($i = 0; $i -lt $region.Count; $i++) {
        $pt1 = $region[$i];
        $skip = $i + 1;
        for ($j = $skip; $j -le $region.Count - $i; $j++) {
            $pt2 = $region[$j];
            $tc = [System.Tuple]::Create((($pt1.Item1 + $pt2.Item1) / 2), (($pt1.Item2 + $pt2.Item2) / 2));
            $dtc = [System.Tuple]::Create(($tc.Item1 - $pt1.Item1), ($tc.Item2 - $pt1.Item2));
            $tr = [Math]::Pow($dtc.Item1, 2) + [Math]::Pow($dtc.Item2, 2);
            if ($tr -lt $radius) {
                $ql = {$region}.Invoke();
                $ql.Remove($pt1);
                $ql.Remove($pt2);
                if (EnclosesPts($tc, $tr, $ql)) {
                    $center = $tc;
                    $radius = $tr;
                }
            }
        }
    }
 
    # Second pass
    for ($i = 0; $i -lt $region.Count; $i++) {
        $pt1 = $region[$i];
        $skip1 = $i + 1;
        for ($j = $skip1; $j -le $region.Count - $skip1; $j++) {
            $pt2 = $region[$j];
            $skip2 = $j + 1;
            for ($k = $skip2; $k -le $region.Count; $k++) {
                $pt3 = $region[$k];
                $fcql = $pt1, $pt2, $pt3;
                $fc = FindCircle($fcql);
                if ($fc.Item1 -lt $radius) {
                    $ql = {$region}.Invoke();
                    $ql.Remove($pt1);
                    $ql.Remove($pt2);
                    $ql.Remove($pt3);
                    if (EnclosesPts([System.Tuple]::Create($fc.Item2[0].Item1, $fc.Item2[0].Item2), $fc.Item1, $ql)) {
                        $center = $fc.Item2;
                        $radius = $fc.Item1;
                    }
                }
            }
        }
    }
 
    if ($radius -eq [float].MaxValue) { $radius =0; }
    else { $radius = [Math]::Sqrt($radius); }
    return [System.Tuple]::Create($radius, $center);
}
 
# simple triangle
function Test1
{
    return [System.Tuple]::Create(0.5, 0.75),
           [System.Tuple]::Create(8.5, 1.63),
           [System.Tuple]::Create(4.87, 6.75);
}
 
# simple box
function Test2
{
    return [System.Tuple]::Create(0, 0),
           [System.Tuple]::Create(0, 5),
           [System.Tuple]::Create(5, 5),
           [System.Tuple]::Create(5, 0);
}
 
# cluster
function Test3
{
    return [System.Tuple]::Create(0.5, 0.75),
           [System.Tuple]::Create(1.25, 0.85),
           [System.Tuple]::Create(3.86, 2.19),
           [System.Tuple]::Create(2.11, 4.65),
           [System.Tuple]::Create(1.17, 2.01),
           [System.Tuple]::Create(3.19, 1.63),
           [System.Tuple]::Create(4.87, 5.39);
}
 
# spread
function Test4
{
    return [System.Tuple]::Create(0.5, 0.75),
           [System.Tuple]::Create(1.25, 0.85),
           [System.Tuple]::Create(3.86, 2.19),
           [System.Tuple]::Create(11, 7),
           [System.Tuple]::Create(1.17, 2.01),
           [System.Tuple]::Create(15, 1.63),
           [System.Tuple]::Create(4.87, 10);
}
 
# circle
function Test5
{
    # trim unwanted output...
    return test5Inner | Where-Object {$_.GetType() -ne [Int32] };
}
 
function test5Inner
{
    # 1 to 360
    $step = 10;
    
    # radius, center x/y
    $r = 3.187;
    $x = 2.685;
    $y = 3.07; 
    
    $rad = [Math]::PI / 180;
    $points = New-Object System.Collections.ArrayList;
 
    for ($i = 0; $i -lt 360; $i += $step) {
        $points.Add([System.Tuple]::Create(($r * [Math]::Cos($i * $rad) + $x), ($r * [Math]::Sin($i * $rad) + $y)));
    }
 
    return $points;
}
 
# ellipse
function Test6
{
    # trim unwanted output...
    return test6Inner | Where-Object {$_.GetType() -ne [Int32] };
}
 
function test6Inner
{
    $step = 1;
    $count = 0; 
    $points = New-Object System.Collections.ArrayList;
 
    # rectangle 10 x 6 =  2, 2, 10, 6 < x, y, width, height
    $rx = 2; $ry = 2; $rw = 10; $rh = 6;
    $Dx = $rx + 10 / 2; $Dy = $ry + 6 / 2; $Rx = $rw / 2; $Ry = $rh / 2;
    $A = 1 / $Rx / $Rx; $B = 1 / $Ry / $Ry; $C = 0; $D = -2 * $Dx / $Rx / $Rx; 
    $E = -2 * $Dy / $Ry / $Ry; $F = $Dx * $Dx / $Rx / $Rx + $Dy / $Ry / $Ry - 1;
 
    for ($x = $Dx - $Rx; $x -le $Dx + $Rx; $x++)
    {
        $r = ($x - $Dx) / $Rx;
        $r = 1 - $r * $r;
        if ($r -ge 0 -and $count % $step -eq 0) {
            $points.Add([System.Tuple]::Create($x, ($Dy + $Ry * [Math]::Sqrt($r))));
        }
        $count++;
    }
    for ($x = $Dx + $Rx; $x -ge $Dx - $Rx; $x--)
    {
        $r = ($x - $Dx) / $Rx;
        $r = 1 - $r * $r;
        if ($r -gt 0 -and $count % $step -eq 0) {
            $points.Add([System.Tuple]::Create($x, ($Dy - $Ry * [Math]::Sqrt($r))));
        }
        $count++;
    }
 
    return $points;
}
 
# ellipse
function Test7
{
    # trim unwanted output...
    return test7Inner | Where-Object {$_.GetType() -ne [Int32] };
}
 
function test7Inner
{
    $count = Get-Random -minimum 2 -maximum 20;
    $points = New-Object System.Collections.ArrayList;
 
    for ($i = 0; $i -le $count; $i++) {
        $points.Add([System.Tuple]::Create((Get-Random -minimum -10.0 -maximum 10.0), (Get-Random -minimum -10.0 -maximum 10.0)));
    }
 
   return $points;
}
 
Main;

Outputs:
--------------------------------------------------------
** TEST: 1 > Triangle - 3 locations ....
 
RADIUS: 4.24581879349343  CENTER: (4.35195051908757, 2.53590437193122)
 
(0.5, 0.75) is on the circle
(8.5, 1.63) is on the circle
(4.87, 6.75) is on the circle
--------------------------------------------------------
** TEST: 2 > Triangle - 4 locations ....
 
RADIUS: 3.53553390593274  CENTER: (2.5, 2.5)
 
(0, 0) is on the circle
(0, 5) is on the circle
(5, 5) is on the circle
(5, 0) is on the circle
--------------------------------------------------------
** TEST: 3 > Cluster - 7 locations ....
 
RADIUS: 3.18694603029295  CENTER: (2.685, 3.07)
 
(0.5, 0.75) is on the circle
(1.25, 0.85) is inside the circle
(3.86, 2.19) is inside the circle
(2.11, 4.65) is inside the circle
(1.17, 2.01) is inside the circle
(3.19, 1.63) is inside the circle
(4.87, 5.39) is on the circle
--------------------------------------------------------
** TEST: 4 > Spread - 7 locations ....
 
RADIUS: 7.49484982443276  CENTER: (7.63802576616104, 3.03502998939203)
 
(0.5, 0.75) is on the circle
(1.25, 0.85) is inside the circle
(3.86, 2.19) is inside the circle
(11, 7) is inside the circle
(1.17, 2.01) is inside the circle
(15, 1.63) is on the circle
(4.87, 10) is on the circle
--------------------------------------------------------
** TEST: 5 > Circle - 36 locations ....
 
RADIUS: 3.187  CENTER: (2.685, 3.07)
 
(5.872, 3.07) is on the circle
(5.82358230884991, 3.62341674222451) is on the circle
(5.67980038244469, 4.16001819677891) is on the circle
(5.44502296186101, 4.6635) is on the circle
(5.12638364022018, 5.118564112071) is on the circle
(4.733564112071, 5.51138364022018) is on the circle
(4.2785, 5.83002296186101) is on the circle
(3.77501819677891, 6.06480038244469) is on the circle
(3.23841674222451, 6.20858230884991) is on the circle
(2.685, 6.257) is on the circle
(2.13158325777549, 6.20858230884991) is on the circle
(1.59498180322109, 6.06480038244469) is on the circle
(1.0915, 5.83002296186101) is on the circle
(0.636435887928999, 5.51138364022018) is on the circle
(0.243616359779818, 5.118564112071) is on the circle
(-0.0750229618610061, 4.6635) is on the circle
(-0.30980038244469, 4.16001819677891) is on the circle
(-0.453582308849907, 3.62341674222451) is on the circle
(-0.502, 3.07) is on the circle
(-0.453582308849907, 2.51658325777549) is on the circle
(-0.30980038244469, 1.97998180322109) is on the circle
(-0.0750229618610057, 1.4765) is on the circle
(0.243616359779817, 1.021435887929) is on the circle
(0.636435887928999, 0.628616359779818) is on the circle
(1.0915, 0.309977038138995) is on the circle
(1.59498180322109, 0.07519961755531) is on the circle
(2.13158325777549, -0.0685823088499071) is on the circle
(2.685, -0.117) is on the circle
(3.23841674222451, -0.0685823088499071) is on the circle
(3.77501819677891, 0.07519961755531) is on the circle
(4.2785, 0.309977038138994) is on the circle
(4.733564112071, 0.628616359779817) is on the circle
(5.12638364022018, 1.021435887929) is on the circle
(5.445022961861, 1.4765) is on the circle
(5.67980038244469, 1.97998180322109) is on the circle
(5.82358230884991, 2.51658325777549) is on the circle
--------------------------------------------------------
** TEST: 6 > Ellispe - 20 locations ....
 
RADIUS: 5  CENTER: (7, 5)
 
(2, 5) is on the circle
(3, 6.8) is inside the circle
(4, 7.4) is inside the circle
(5, 7.7495454169735) is inside the circle
(6, 7.93938769133981) is inside the circle
(7, 8) is inside the circle
(8, 7.93938769133981) is inside the circle
(9, 7.7495454169735) is inside the circle
(10, 7.4) is inside the circle
(11, 6.8) is inside the circle
(12, 5) is on the circle
(11, 3.2) is inside the circle
(10, 2.6) is inside the circle
(9, 2.2504545830265) is inside the circle
(8, 2.06061230866019) is inside the circle
(7, 2) is inside the circle
(6, 2.06061230866019) is inside the circle
(5, 2.2504545830265) is inside the circle
(4, 2.6) is inside the circle
(3, 3.2) is inside the circle
--------------------------------------------------------
** TEST: 7 > Random - 16 locations ....
 
RADIUS: 10.4807711313096  CENTER: (1.51226096426611, 1.06697417588485)
 
(9.36798405804112, 3.9484739554806) is inside the circle
(2.0232408270348, -0.0466210628145465) is inside the circle
(1.34948981523024, 5.79217375060179) is inside the circle
(-2.30419161371151, 9.13549994078255) is inside the circle
(1.98685468732699, -1.24412047269015) is inside the circle
(-7.25088334514335, -4.6822749332908) is on the circle
(9.52689506091498, 2.66917036504912) is inside the circle
(0.0586286140878816, 1.60198716987017) is inside the circle
(-1.0043472289128, -9.10717181819825) is on the circle
(2.48952382825759, -2.79195825233681) is inside the circle
(5.51393311261848, 9.75337995204766) is inside the circle
(-1.806139392688, -5.54147382990526) is inside the circle
(-4.75848675461416, -5.67003791018857) is inside the circle
(1.75757037091887, 2.86631366837133) is inside the circle
(9.60481588710324, 7.72708816347974) is on the circle
(-1.25076149182895, 0.426093931508294) is inside the circle
 
--------------------------------------------------------
7 Tests run. Scroll up to see results.
  Permalink  
v10
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 8

A really basic PowerShell solution:

    $Coords = @(
        @(100,50)
        ,@(50,50)
        ,@(10,30)
        ,@(100,30)
        ,@(102,90)
        ,@(80,60)
        ,@(40,110)
    )
 
    $center = $Coords | %{
        $a = $_
        $Coords | %{
            $b = $_
            $x = $a[0] - $b[0]
            $y = $a[1] - $b[1]
            $d = [Math]::Pow([Math]::Pow($x,2) + [Math]::Pow($y,2),1/2)
            (new-object -TypeName PSObject -Property @{
                Distance = $d
                X = ($a[0] + $b[0]) / 2.0
                Y = ($a[1] + $b[1]) / 2.0
            })
        }
    } | sort Distance -descending | select -First 1
 

 
    #code to draw this
    [reflection.assembly]::LoadWithPartialName("System.Windows.Forms") | out-null
    [reflection.assembly]::LoadWithPartialName("System.Drawing") | out-null
    $container = new-object Drawing.SolidBrush green
    $point = new-object Drawing.SolidBrush black
    $form = New-Object Windows.Forms.Form
    $formGraphics = $form.createGraphics()
    $form.add_paint({
        $formGraphics.FillEllipse($container, ($center.X - $center.Distance/2), ($center.Y - $center.Distance/2), $center.Distance, $center.Distance) #adjust to use upper left instead of center of circle
        $Coords | %{$formGraphics.FillEllipse($point, ([int]$_[0]), ([int]$_[1]), 10, 10)}
    })
    $form.ShowDialog()  
  Permalink  
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 10

Depending on the data the 'solution' circle will be defined either by
a) two points (these two points define circle diameter) [^]
b) OR three points (these three points are on the 'solution' circle) [^]

That's said we may do the following:

1) find two most distant points, consider them being our circle candidate diameter and check if all other points are within boundaries of the circle candidate. if success - we've just found the (a) type solution;

2) if not, continue with probing circle candidates defined by data set point triplets, searching for a minimum radius among qualified circle candidates.

The code below will read space-delimited point data and output a space delimited circle center x y and circle radius:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct point {
    double  x, y;
} point_t;
 
static int err ( const char *msg, int code ) {
    fputs ( msg, stderr );
    return code;
}
 
static double distance ( point_t *p1, point_t *p2 ) {
    double dx = p1->x - p2->x;
    double dy = p1->y - p2->y;
    return sqrt(dx*dx + dy*dy);
}
 
// this one will find a pair of points with a maximum
// distance between them, storing their indicies into
// i1 and i2 respectively
static double search_max_distance (
    point_t *points,
    size_t n,
    size_t *_i,
    size_t *_j
) {
    size_t  i, j;
    double  max_d = 0.0;
    *_i = *_j = 0;
    for ( i = 0; i < n; i++ )
    for ( j = i+1; j < n; j++ ) {
        double  d = distance(points+i, points+j);
        if ( d > max_d ) {
            max_d = d;
            *_i = i;
            *_j = j;
        }
    }
    return max_d;
}
 
// circle through 3 points voodoo
// http://mathforum.org/library/drmath/view/54323.html
// returns radius of a circle, fills 'center' point
static double circle_vvv (
    point_t *p1,
    point_t *p2,
    point_t *p3,
    point_t *center,
    double  line_threshold
) {
    double x1=p1->x, x2=p2->x, x3=p3->x;
    double y1=p1->y, y2=p2->y, y3=p3->y;
    double temp = x2*x2 + y2*y2;
    double bc = (x1*x1 + y1*y1 - temp) / 2.0;
    double cd = (temp - x3*x3 - y3*y3) / 2.0;
    double det = (x1-x2)*(y2-y3) - (x2-x3)*(y1-y2);
    if ( fabs(det) < line_threshold ) {
        // assume they are on a single line
        return 0.0;
    }
    center->x = (bc*(y2-y3) - cd*(y1-y2)) / det;
    center->y = ((x1-x2)*cd - (x2-x3)*bc) / det;
    return distance(center, p1);
}
 
int main() {
    double line_threshold = 1e-7, min_radius;
    point_t *points = NULL, min_center, p;
    size_t n = 0, n_alloc = 0, i, j, k, l, n_circles;
 
    // read all points into dynamically allocated memory
    while ( scanf ( " %lE %lE", &p.x, &p.y ) == 2 ) {
        if ( n == n_alloc ) {
            n_alloc += 1000;
            points = realloc ( points, sizeof*points * n_alloc );
            if ( !points ) return err ( "no memory?!!", 1 );
        }
        points[n] = p;
        n++;
    }
 
    // PART ZERO: couple of corner cases
    if ( n == 0 ) return err ( "no points", 2 );
    else if ( n == 1 ) {
        min_center = points[0];
        min_radius = 0.0;
        goto success;   // I am going to regret this after seeing comments...
    }
 
    // PART I: look for a 'two point win' - get two most distant points, assume
    // we've found a circle diameter and check if all other points are within
    // this particular circle
    min_radius = search_max_distance ( points, n, &i, &j ) / 2.0;
    min_center.x = (points[i].x + points[j].x) / 2.0;
    min_center.y = (points[i].y + points[j].y) / 2.0;
    for ( k = 0; k < n; k++ ) {
        if ( k == i || k == j ) continue;
        if ( distance(&min_center, points+k) > min_radius ) break;
    }
    if ( k == n ) goto success; // I just can't help myself...
 
    // PART II: continue with probing all circles defined by a set of
    // circles defined by point triplets
    n_circles = 0;
    for ( i = 0; i < n; i++ )
    for ( j = i+1; j < n; j++ )
    for ( k = j+1; k < n; k++ ) {
        point_t center;
        double  radius = circle_vvv (
            points+i,
            points+j,
            points+k,
            ¢er,
            line_threshold
        );
        if ( radius == 0.0 ) continue;  // skip an undefined circle
        for ( l = 0; l < n; l++ ) {
            if ( l == i || l == j || l == k ) continue;
            if ( distance(¢er, points+l) > radius ) break;
        }
        if ( l != n ) continue; // no fit
        if ( !n_circles || radius < min_radius ) {
            min_radius = radius;
            min_center = center;
            n_circles++;
        }
    }
    if ( !n_circles ) return err ( "weird, no solution found", 3 );
success:
    printf ( "% E  % E  % E\n", min_center.x, min_center.y, min_radius );
    return 0;
}


Given the brute-force flavor of the code above one can actually consider merging both phases into one search (where 2-point case is considered being a corner case for a 3-point candidate evaluation phase). Below code implements this 'single flow' idea (certainly being less efficient than the above version when it comes to finding a 2-point solution). Actually this one is the first I wrote for a challenge:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef struct point {
    double  x, y;
} point_t;
 
static int err ( const char *msg, int code ) {
    fputs ( msg, stderr );
    return code;
}
 
int main() {
    double line_threshold = 1e-7, min_radius;
    struct point *points = NULL, min_center, p;
    size_t n = 0, n_alloc = 0, i, j, k, l, n_circles = 0;
 
    // read all points into dynamically allocated memory
    while ( scanf ( " %lE %lE", &p.x, &p.y ) == 2 ) {
        if ( n == n_alloc ) {
            n_alloc += 1000;
            points = realloc ( points, sizeof*points * n_alloc );
            if ( !points ) return err ( "no memory?!!", 1 );
        }
        points[n] = p;
        n++;
    }
 
    // couple of corner cases
    if ( n == 0 ) return err ( "no points", 2 );
    else if ( n == 1 ) {
        min_center = points[0];
        min_radius = 0.0;
        goto success;   // I am going to regret this after seeing comments...
    }
 
    // brutforcing the challenge and merging a two-point and three-point
    // cases into one program flow
    for ( i = 0; i < n; i++ ) {
        for ( j = i+1; j < n; j++ ) {
            for ( k = j; k < n; k++ ) {
                double x1=points[i].x, x2=points[j].x, x3=points[k].x;
                double y1=points[i].y, y2=points[j].y, y3=points[k].y;
                double dx, dy, radius;
                struct point center;
                if ( k == j ) {
                    // minimal diameter circle through on two points
                    // (these two points define diameter in this case)
                    center.x = (x1+x2)/2.0;
                    center.y = (y1+y2)/2.0;
                } else {
                    // circle through 3 points black magic
                    // http://mathforum.org/library/drmath/view/54323.html
                    // inlined math loks weird...
                    double temp = x2*x2 + y2*y2;
                    double bc = (x1*x1 + y1*y1 - temp) / 2.0;
                    double cd = (temp - x3*x3 - y3*y3) / 2.0;
                    double det = (x1-x2)*(y2-y3) - (x2-x3)*(y1-y2);
                    double dx, dy;
                    if ( fabs(det) < line_threshold ) {
                        // assume they are on a single line and have been
                        // either covered or will be covered in future by
                        // a two point case OR it was some crazy corner case
                        continue;
                    }
                    center.x = (bc*(y2-y3) - cd*(y1-y2)) / det;
                    center.y = ((x1-x2)*cd - (x2-x3)*bc) / det;
                }
                dx = x1 - center.x;
                dy = y1 - center.y;
                radius = sqrt ( dx*dx + dy*dy );
 
                // check if all points are within candidate circle
                // (assume that i,j,k points are already within)
                for ( l = 0; l < n; l++ ) {
                    if ( l == i || l == j || l == k ) continue;
                    dx = points[l].x - center.x;
                    dy = points[l].y - center.y;
                    if ( dx*dx + dy*dy > radius*radius ) break;
                }
                if ( l != n ) continue;
                //fprintf ( stderr, "%E %E %E\n", center.x, center.y, radius );
                if ( !n_circles || radius < min_radius ) {
                    min_radius = radius;
                    min_center = center;
                    n_circles++;
                }
            }
        }
    }
    if ( !n_circles ) return err ( "weird, no circle found", 3 );
success:
    printf ( "% lE  % lE  % lE\n", min_center.x, min_center.y, min_radius );
    return 0;
}


Trust but verify, right? Both versions are a command line tools reading stdin and writing stdout. Here is a test bench using 'system()' call to invoke a 'circle' binary feeding it with random points, capturing its output and verifying if all generated points are within a circle. BTW, they are not because of precision issues related to using human-readable form of floating point number at both input and output compared to original full-precision data inside test program. What I did is that I measured how far an 'erroneous' points are outside of the circle compared to circle radius. Think of 1e-6 absolute error when circle radius is 4 or so. Looks like a rounding errors to me. Here's the test code:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
 
static double frand_range(double range) {
    return range * rand() / RAND_MAX - range / 2.0;
}
 
int main(int argc, char *argv[]) {
    size_t  i, j, k, l;
    double  range = 10.0;
    double  threshold = 1e-5;
    double  eps_min = 1e-6;
 
    srand ( time(NULL) );
    for ( i = 1; i <= 100; i++ ) {
        size_t  n = i <= 3 ? 10 : 5;  // times
        double  *x = malloc(sizeof*x * i);
        double  *y = malloc(sizeof*y * i);
        double  max_error = 0.0;
        double  max_error_r = 0.0;
        int retcode;
        printf ( "%d:", i );
        if ( !x || !y ) {
            printf ( "one of those low memory days...\n" );
            return 1;
        }
        for ( j = 0; j < n; j++ ) {
            FILE    *fp = fopen ( "points", "wt" );
            for ( k = 0; k < i; k++ ) {
                x[k] = frand_range(range);
                y[k] = frand_range(range);
                fprintf ( fp, "% E  % E\n", x[k], y[k] );
            }
            fclose ( fp );
            retcode = system ( "circle < points > c" );
            printf ( ".%d", j+1 );
            if ( retcode ) {
                printf ( "retcode=%d\n", retcode );
                return 2;
            } else {
                double  cx, cy, r, eps;
                fp = fopen ( "c", "rt" );
                if ( !fp || fscanf ( fp, " %lE %lE %lE", &cx, &cy, &r ) != 3 ) {
                    printf ( "why?!!\n" );
                    return 3;
                }
                fclose(fp);
                eps = r * threshold;
                if ( eps < eps_min ) eps = eps_min;
                if ( r == 0.0 ) r = eps_min;
                for ( l = 0; l < i; l++ ) {
                    double dx=cx-x[l];
                    double dy=cy-y[l];
                    double d = sqrt(dx*dx+dy*dy);
                    if ( d > r+eps ) {
                        printf ( "err=%lg d=%lg dx=%lg dy=%lg\n", d-r, d, dx, dy );
                        return 4;
                    }
                    if ( d > r ) {
                        double err = d-r;
                        if ( err > max_error ) {
                            max_error = err;
                            max_error_r = r;
                        }
                    }
                }
            }
        }
        free(x);
        free(y);
        printf ( " max_err=%lg (r=%lg)\n", max_error, max_error_r );
    }
    return 0;
}


All of the above has been tested on a Windows 10 box using Tiny C Compiler TCC : Tiny C Compiler[^]. If you haven't heard of it yet - give it a try. For example - it produces 3072 bytes executable from the second version of the solution (32-bit tcc 0.9.25).

UPDATE 1
I am not sure if delivering compact solution can be qualified as an interesting use of a language, but still.

Below is a 40 LOC main() (with 80 chars per line limit obeyed) version of the mathematically correct solution that can detect errors and process corner cases same as above versions. My point is that despite its being raw it is still human-readable. What do you think?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main() {
    struct dot {double x,y;} *dots=NULL;
    size_t n=0;
    double r=0.0;
    for(n=0;;n++) {
        if(!(n%1024)) if(!(dots=realloc(dots,sizeof*dots*(n+1024)))) return 1;
        if(scanf(" %lE %lE", &dots[n].x, &dots[n].y)!=2) break;
    }
    if(!n) return 2;
    else if (n>1) {
        double x, y;
        size_t i, j, k, l, cnum=0;
        for(i=0;i<n;i++)
        for (j=i+1;j<n;j++)
        for (k=j;k<n;k++) {
            double x1=dots[i].x, x2=dots[j].x, x3=dots[k].x;
            double y1=dots[i].y, y2=dots[j].y, y3=dots[k].y;
            double cx=(x1+x2)/2, cy=(y1+y2)/2;
            double t=x2*x2+y2*y2, bc=(x1*x1+y1*y1-t)/2, cd=(t-x3*x3-y3*y3)/2;
            double d=(x1-x2)*(y2-y3)-(x2-x3)*(y1-y2), rsq;
            if(k!=j) {
                if(d==0.0) continue;
                cx=(bc*(y2-y3)-cd*(y1-y2))/d;
                cy=((x1-x2)*cd-(x2-x3)*bc)/d;
            }
            rsq=(cx-x1)*(cx-x1)+(cy-y1)*(cy-y1);
            for(l=0;l<n;l++) {
                double dx=dots[l].x-cx, dy=dots[l].y-cy;
                if(l==i || l==j || l==k) continue;
                if(dx*dx+dy*dy > rsq) break;
            }
            if(l!=n || cnum && rsq>r*r) continue;
            cnum++; r=sqrt(rsq); x=cx; y=cy;
        }
        if(!cnum) return 3;
        dots[0].x=x; dots[0].y=y;
    }
    printf("% lE  % lE  % lE\n",dots[0].x, dots[0].y, r);
    return 0;
}
  Permalink  
v2
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 13

I was late because I was misinformed that the
Quote:
... challenge is a simple one:

Nevertheless, I took a second look, suddenly these stuff started haunting me, geometry, linear algebra, slope, y-intercept, and whatnot. Look that the only way to free myself from the nightmare is to take on this "simple" challenge. As a result, I came out with the following assumption and algorithm:
1.  The smallest circle must include at least two of the points on its circumference.
2.  In order to encircle as many points as possible, these two points must be as far apart as possible.
3.  Seek out three pairs of furthest points in the set.
4.  For each pair, 
    4.1 Draw the bisector line where the center of circle lies
    4.2 Draw the line joining the pair of points
    4.3 Designate the intersect between these 2 lines as the center of circle and the half distance of the pair as radius
    4.4 Draw a cicle
    4.5 Gather all points that fall outside of the circle, call them outliers
    4.6 Check out which side of this line (in 4.2) the outliers lie
        4.6.1  IF they are on the different sides, then reject this pair as potential, ELSE
        4.6.2  MOVE the center of circle towards the side where the outliers lie and calculate new radius
    4.7 Repeat 4.4 to 4.6 until there is no more outliers, mark the pair as potential.
5.  The solution will be the one with the smallest radius!

Now that I have got the plan, what tool should I use to implement it? I would like to have a tool that allows me to visualize the result in graphical points, lines, and circles with minimum code. Got it! R is the one! Here you are, my implementation in R:
################################################################
# Coding challenge: smallest circle to surround a set of points
#      Submitted by Peter Leow the circle haunter
################################################################
 
require(plotrix)
 
# The set of x, y points in contention!
# Assume min 3 points
# Uncomment to try out different test sets
x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,1.7,2.2);
y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);
 
# x <- c(1.2,4.7,1.9,4.1,3.6,3.3,4.9,1.4,2.8,1.8,1.7,2.2);
# y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);
 
# x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,4.7,2.2);
# y <- c(3.1,4.7,2.0,5.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);
 
# Turn x, y into a list of point vectors
all_points <- mapply( c , x , y , SIMPLIFY = FALSE )
 
# Number of furthest pairs of points
num_furthest_pairs <- 3
 
# Vector of colors
colors = c("red","green","blue")
 
# Meet them in a plot
plot(x, y, main="Seeing is Believing in R by Peter Leow", 
  xlab="X", ylab="Y",
  xlim=c(0, 10), ylim=c(0, 10))
axis(side=1, at=c(0:10))
axis(side=2, at=c(0:10))
 

# function to calculate Euclidean distance between 2 points
calEuclideanDistance <- function(point1, point2){
    
    return (sqrt((point1[1]-point2[1])^2 + (point1[2]-point2[2])^2))
    
}
 
# function to find pairs of furthest points
findPairsOfFurthestPoints <- function(all_points){
    
    furthest_pairs <- list()
    
    for (n in 1:num_furthest_pairs){
        
        furthest_distance <- 0
        
        for (i in 1:(length(all_points)-1)) {
        
            for (j in i+1:(length(all_points)-i)) {
                  
                b <- c(all_points[[i]], all_points[[j]])
                
                if (n > 1 & Position(function(x) identical(x, b), furthest_pairs, nomatch = 0) > 0) next
                                    
                distance <- calEuclideanDistance(all_points[[i]], all_points[[j]])
 
                if (distance > furthest_distance) {
                
                    furthest_distance <- distance
                    
                    furthest_pairs[[n]] <- c(all_points[[i]], all_points[[j]])
                    
                    furthest_pairs[[n]] 
                }
            
            }
 
        }
        
    }
 
    return (furthest_pairs) # return a list containing num_furthest_pairs of pairs of furthest points in descending order
}
 
# Find 3 pairs of further points
pairsOfFurthestPoints <- findPairsOfFurthestPoints(all_points)
 
cat("The",num_furthest_pairs,"furthest pairs (x1 y1 x2 y2):\n")
cat("Pair #1 (Red)  :",pairsOfFurthestPoints[[1]],"\n") # first furthest pair
cat("Pair #2 (Green):",pairsOfFurthestPoints[[2]],"\n") # second furthest pair
cat("Pair #3 (Blue) :",pairsOfFurthestPoints[[3]],"\n") # third furthest pair                         
 
# Check out the pairs visually!                                  
for (p in 1:num_furthest_pairs) {
    
    points(pairsOfFurthestPoints[[p]][1],pairsOfFurthestPoints[[p]][2],cex=2,pch=4,col=colors[p])
    
    points(pairsOfFurthestPoints[[p]][3],pairsOfFurthestPoints[[p]][4],cex=2,pch=4,col=colors[p])
    
    center <- c(pairsOfFurthestPoints[[p]][1] + pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][2] + pairsOfFurthestPoints[[p]][4]) / 2
 
    radius <- calEuclideanDistance(c(pairsOfFurthestPoints[[p]][1], pairsOfFurthestPoints[[p]][2]), c(pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][4])) / 2
 
    #points(center[1],center[2],cex=2,pch=18,col=colors[p])
    #draw.circle(center[1], center[2], radius,border=colors[p])
}
 
# function to find the line of two points
findLinearEquation <- function(point1, point2){
 
    # m = slope
    m <- (point2[2]-point1[2]) /(point2[1]-point1[1])
    
    # b = y - mx, the (y-intecept)
    b <- point1[2] - m * point1[1]
    
    return (c(m, b)) # slope, y-intercept
}                                     
                                     
# function to find the bisector line of two points
findBisectorEquation <- function(point1, point2){
 
    mid_point <- (point1 + point2) / 2
    
    slope <- (point2[2]-point1[2]) /(point2[1]-point1[1])
    
    # slope of the perpendicular bisector line
    # y = mx + b
    m <- -1 / slope
    
    # b= y - mx
    b <- mid_point[2] - m * mid_point[1]
    
    return (c(m, b)) # slope, y-intercept
}                                     
                                     
                                     
# function to find the smallest circle that crosses the pair of points
findSmallestCircle <- function(pair, all_points, pair_no){
 
    point1 <- pair[1:2]
 
    point2 <- pair[3:4]
  
    points <- list()
    
    n <- 0
    
    # exclude the pair from the rest of the points
    for (i in 1:length(all_points)) {
                
        if (!all(point1 == all_points[[i]]) & !all(point2 == all_points[[i]])) {
            
            n <- n + 1
            
            points[[n]] <- all_points[[i]]
                   
        } 
    }
      
    # (c(m, b)) # slope, y-intercept
    line = findLinearEquation(point1, point2)
 
    # Plot a line thru the pair of points
    abline(b=line[1], line[2], col=colors[pair_no])
    
    # slope, y-intercept
    bisector_line = findBisectorEquation(point1, point2)
    
    # Draw the bisector line to the pair of points
    abline(b=bisector_line[1], a=bisector_line[2], col=colors[pair_no])
    
    radius <- calEuclideanDistance(point1, point2) / 2
    
    center <- c(point1[1] + point2[1], point1[2] + point2[2]) / 2
    
 
    while (TRUE) {
    # Find all the points outside of the circle
    outliers <- list()
        
    q = 0
 
    for (i in 1:length(points)) {
                
        if (calEuclideanDistance(center, points[[i]]) > radius) {
            
            q <- q + 1
            
            outliers[[q]] = points[[i]]
            
            # cat("Outlier (x y):", outliers[[q]], "\n")
          
        } 
    }
        
    # if there is no outliers, then this point is one of the potential circle!
    if (q==0) {
        return (c(center, radius))
    }
    
    # Detemine which side of the line each outlier lies
    sides <- list()
    
    outlier_b <- list() # list of outlier y-intercepts
    
    for (i in 1:length(outliers)) {
        
        # find the y-intercep of the outlier line parallel to the line
        # b = y - mx
        outlier_b[[i]] <- outliers[[i]][2] - line[1] * outliers[[i]][1]
        
        # find the difference between the two y-intercepts
        sides[[i]] <- line[2] - outlier_b[[i]]
    }
    
    # If not all outliers on the same side, then reject this point
    if (!(all(sides > 0) | all(sides < 0))) {
        return (c(center, -1)) # assign -1 to radius to indicate rejection
    }
    
    move_x <- 0.1
        
    new_center_x <- 0
    
    if (all(sides > 0)) {
 
        new_center_x <- center[1] - move_x
 
    } else {
        
        new_center_x <- center[1] + move_x
  
    }
        
    new_center_y <- bisector_line[1] * new_center_x + bisector_line[2]
        
    new_center <- c(new_center_x, new_center_y)
        
    new_radius <- calEuclideanDistance(new_center, point1)
        
    draw.circle(new_center[1], new_center[1], new_radius,border=colors[pair_no])
        
    center <- new_center
    radius <- new_radius  
        
    #print(center)
    #print(radius)
        
    
  } # End of while
    
}   
 
for (i in 1:length(pairsOfFurthestPoints)){                                   
                                     
    smallestCircle <- findSmallestCircle(pairsOfFurthestPoints[[i]], all_points, i)  
    
    if (smallestCircle[3] != -1) {
        
        # a potential solution
        draw.circle(smallestCircle[1], smallestCircle[1], smallestCircle[3], border="black")
        
    }
 
    cat ("Result of Pair #", i, " (centerX, centreY, radius):", smallestCircle, "\n")
    
}
 
print("Note: The potential solutions are those pairs with positive radius and plotted in black circles!")

See it live at Coding challenge: smallest circle to surround a set of points, R - rextester[^]
The code has been commented for easy reading and understanding.
Try out the different test sets, increase the number of pair of furthest points, change the increment of move_x, and have fun!
This online tester may freeze if the load is too much, do handle with love.
Finally, I am free from the geometrical nightmare!
+++++[Round 2]+++++
ppolymorphe:
Quote:
I fear your solution need some refinement.
For your first dataset, I get cenrze {3.36,3.00} and radius 2.16

Fear not, if you change the parameter
move_x
to 0.01, you will get a closer answer, try it. This is an optimization process.
+++++[Closing Words]+++++
After a good night sleep, I will now have the closing words. There are already well-known algorithms for solving such a problem, but they are not my cup of tea. As some of you have tried my code, I have turned this challenge into an optimization one. In fact, there are a number of parameters that you can change to optimize the results. If you dare, you can add addition code to automate this optimization process by changing these parameters based on some fitness function that will evolve results that move gradually towards the most optimal one on each iteration . You can even animate the outcome by re-plotting the circle on each iteration. Sky is not even the limit anymore. This is an added "code challenge" on my own accord, I hope I did not commit any copyright infringement.
In fact, I have already got myself a prize, i.e. the R language that I picked up while I coded for this challenge. So forgive me if the code is not optimized as I am a newbie to R.
Quote:
DISCLAIMER: This code is supplied as it is, your use of any part of it is at your own risk. Signed off by Peter Leow
  Permalink  
v10
Comments
ppolymorphe 11-Jan-17 10:11am
   
I fear your solution need some refinement.
For your first dataset, I get cenrze {3.36,3.00} and radius 2.16
Peter Leow 11-Jan-17 11:11am
   
Thank you for trying out my code. Reply added in my solution.
ppolymorphe 11-Jan-17 21:29pm
   
I consider changing move_x a refinement since it lead to better solution.
Peter Leow 11-Jan-17 21:32pm
   
You are welcome.
Graeme_Grant 11-Jan-17 11:17am
   
I agree with ppolymorphe. To help you, here is what I am seeing:

--------------------------------------------------------
** TEST: 1 > Peter Leow - Set 1 - 12 locations ....

RADIUS: 2.158829 Center: (3.356944,3.009809)

(1.2,3.1) is on the circle
(4.7,4.7) is on the circle
(1.9,2) is inside the circle
(2.1,3.5) is inside the circle
(3.6,3.5) is inside the circle
(2.3,4.6) is inside the circle
(4.9,1.5) is on the circle
(1.4,3.2) is inside the circle
(2.1,2.3) is inside the circle
(1.8,2.3) is inside the circle
(1.7,3.5) is inside the circle
(2.2,2.4) is inside the circle
--------------------------------------------------------
** TEST: 2 > Peter Leow - Set 2 - 12 locations ....

RADIUS: 2.158829 Center: (3.356944,3.009809)

(1.2,3.1) is on the circle
(4.7,4.7) is on the circle
(1.9,2) is inside the circle
(4.1,3.5) is inside the circle
(3.6,3.5) is inside the circle
(3.3,4.6) is inside the circle
(4.9,1.5) is on the circle
(1.4,3.2) is inside the circle
(2.8,2.3) is inside the circle
(1.8,2.3) is inside the circle
(1.7,3.5) is inside the circle
(2.2,2.4) is inside the circle
--------------------------------------------------------
** TEST: 3 > Peter Leow - Set 3 - 12 locations ....

RADIUS: 2.441311 Center: (3.5,3.5)

(1.2,3.1) is inside the circle
(4.7,4.7) is inside the circle
(1.9,2) is inside the circle
(2.1,5.5) is on the circle
(3.6,3.5) is inside the circle
(2.3,4.6) is inside the circle
(4.9,1.5) is on the circle
(1.4,3.2) is inside the circle
(2.1,2.3) is inside the circle
(1.8,2.3) is inside the circle
(4.7,3.5) is inside the circle
(2.2,2.4) is inside the circle
Peter Leow 11-Jan-17 11:19am
   
See added reply to my solution.
Graeme_Grant 11-Jan-17 11:24am
   
yes, I see. I was replying to you when you replied to ppolymorphe. :)

The solution that we used, in a nutshell, was to: find the outer max points, remove the inner points (not required), then find the best fit with the remaining points.
Peter Leow 11-Jan-17 11:30am
   
Yes. Thank you for trying out my code.
Graeme_Grant 11-Jan-17 11:36am
   
Looks good with the adjustment. :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 14

Maybe a bit late to the party, but I worked hard...
Coding Challenge: Smallest Circle Problem[^]
  Permalink  
v2
Comments
Graeme_Grant 12-Jan-17 5:47am
   
Close, but the 3rd set's smallest circle is smaller than your results. Here is what we found:

--------------------------------------------------------
** TEST: 3 > Kornfeld Eliyahu Peter - Set 3 - 5 locations ....

RADIUS: 5 Center: (5,2)

(2,-2) is on the circle
(5,1) is inside the circle
(4,3) is inside the circle
(2,2) is inside the circle
(8,6) is on the circle
Kornfeld Eliyahu Peter 12-Jan-17 5:57am
   
If you following the logic of the article you will see, that the logic in there will lead to your solution... exactly, however I have some bug in the point removing functionality and one of the inner point no removed... I will check it and update you and the code...
Graeme_Grant 12-Jan-17 6:02am
   
Your method is very similar to ours. I hope that you find your problem. I have some additional datasets (solution 7) that you can test with.
Kornfeld Eliyahu Peter 12-Jan-17 6:04am
   
Thank you...
It is also important, that my primary goal wasn't to give a perfect algorithm, but more talk about the idea of approaching a solution...
Graeme_Grant 12-Jan-17 6:49am
   
Glad to see that you fixed your problem! :)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 15

My solution with a real program. Clipper language (mostly FoxPro)
The method:
1) find the farthest 2 points from each others.
2) try the 2 points on circle solution, center is in the middle of the 2 points.
3) if a point a farther than the radius, the 2 points solution don't work.
4) switch to 3 points on circle solution.
5) search 3 farthest points from center.
6) move center closer to farthest point.
7) repeat at 5 until 3 farthest points are same distance.
*   CCCP Code Challenge Code Project
* Circle surounding dataset in plane
clear
CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } })
 
CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39} })
 
return
 
function Circlefit(data)
	clear
	@ 2, 0 say "CCCP Code Challenge Code Project"
	@ 3, 0 say "Circle surrounding dataset in plane"
	dist= array(len(data))
	
	tours=0
	* Solve 2 Points
	* trouver les 2 points les + eloignes
	d1= 0
	p3= 0
	for scan1=1 to len(data)-1
		for scan2=scan1+1 to len(data)
			tmp= sqrt((data[scan1,1]-data[scan2,1])^2+(data[scan1,2]-data[scan2,2])^2)
			if tmp > d1
				p1= scan1
				p2= scan2
				d1= tmp
			endif
		next
	next
	bestx= (data[p1,1]+ data[p2,1])/2
	besty= (data[p1,2]+ data[p2,2])/2
	bestr= Calc_Rad(data, bestx, besty, dist)
	if bestr - d1/2 > 0.0001
		* Solve 3 Points
		sol= "3 points"
		while .T.
			tours ++
			p1= 0
			d1= 0
			p2= 0
			d2= 0
			p3= 0
			d3= 0
			*	chercher les 3 points les + eloignes du centre
			for scan=1 to len(data)
				if dist[scan] > d1
					p3=p2
					d3=d2
					p2=p1
					d2=d1
					p1=scan
					d1=dist[scan]
				elseif dist[scan] > d2
					p3=p2
					d3=d2
					p2=scan
					d2=dist[scan]
				elseif dist[scan] > d3
					p3=scan
					d3=dist[scan]
				endif
			next
			aff()
			* converge vers p1
			bestx= bestx+ (data[p1,1]-bestx)*(d1-d3)/d1/2
			besty= besty+ (data[p1,2]-besty)*(d1-d3)/d1/2
			bestr= Calc_Rad(data, bestx, besty, dist)
			if d1-d3 < 0.0001
				exit
			endif
		enddo
		sol= "Solution a 3 points"
	else
		sol= "Solution a 2 points"
	endif
	aff()
	return
 
procedure aff()
	@ 5, 0 say bestx picture "@E 99.9999"
	@ 5,10 say besty picture "@E 99.9999"
	@ 5,20 say bestr picture "@E 99.9999"
	@ 5,30 say tours picture "999"
	@ 5,40 say sol
	for scan=1 to len(data)
		@ 6+scan, 0 say data[scan,1] picture "@E 99.99"
		@ 6+scan,10 say data[scan,2] picture "@E 99.99"
		if scan= p1
			@ 6+scan,18 say "1"
		elseif scan= p2
			@ 6+scan,18 say "2"
		elseif scan= p3
			@ 6+scan,18 say "3"
		else
			@ 6+scan,18 say " "
		endif
		@ 6+scan,20 say dist[scan] picture "@E 99.9999"
	next
	inkey(0)
	return
 
function Calc_Rad(data, cx, cy, dist)
	*	calcul des rayons
	cr= 0
	for scan=1 to len(data)
		dist[scan]= sqrt((cx-data[scan,1])^2+(cy-data[scan,2])^2)
		if cr < dist[scan]
			cr= dist[scan]
		endif
	next
	return cr

[Update]
Results:
dataset 1
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }
Solution is 3 points on circle
Center is {1.7276,2.5255} Radius os 2.1586 with 16 iterations

dataset 2
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39} }
Solution is 2 points on circle
Center is {2.6850,3.0700} Radius os 3.1869

[Update] Here is a dump of display for full solution of the 3 sets
CCCP Code Chalenge Code Project
Circle surounding dataset in plane
 
 1,3050    2,7000    2,6054     0       2 points
 
 0,50      0,75   1  2,1096
 1,25      0,85      1,8508
 3,86      2,19      2,6054
 2,11      4,65   2  2,1096
 1,17      2,01      0,7031
 3,19      1,63      2,1675
 
 1,3050    2,7000    2,6054     1       3 points
 
 0,50      0,75   3  2,1096
 1,25      0,85      1,8508
 3,86      2,19   1  2,6054
 2,11      4,65      2,1096
 1,17      2,01      0,7031
 3,19      1,63   2  2,1675
 
 1,5481    2,6515    2,3575     2       3 points
 
 0,50      0,75   2  2,1712
 1,25      0,85      1,8260
 3,86      2,19   1  2,3575
 2,11      4,65   3  2,0760
 1,17      2,01      0,7446
 3,19      1,63      1,9337
 
 1,6861    2,6239    2,2178     3       3 points
 
 0,50      0,75   1  2,2178
 1,25      0,85      1,8267
 3,86      2,19   2  2,2168
 2,11      4,65   3  2,0699
 1,17      2,01      0,8020
 3,19      1,63      1,8026
 
 1,6466    2,5615    2,2444     4       3 points
 
 0,50      0,75   2  2,1439
 1,25      0,85      1,7568
 3,86      2,19   1  2,2444
 2,11      4,65   3  2,1393
 1,17      2,01      0,7289
 3,19      1,63      1,8027
 
 1,6984    2,5528    2,1918     5       3 points
 
 0,50      0,75   2  2,1648
 1,25      0,85      1,7608
 3,86      2,19   1  2,1918
 2,11      4,65   3  2,1372
 1,17      2,01      0,7575
 3,19      1,63      1,7540
 
 1,7253    2,5483    2,1760     6       3 points
 
 0,50      0,75   1  2,1760
 1,25      0,85      1,7635
 3,86      2,19   2  2,1645
 2,11      4,65   3  2,1367
 1,17      2,01      0,7734
 3,19      1,63      1,7287
 
 1,7142    2,5320    2,1729     7       3 points
 
 0,50      0,75   2  2,1563
 1,25      0,85      1,7449
 3,86      2,19   1  2,1729
 2,11      4,65   3  2,1547
 1,17      2,01      0,7541
 3,19      1,63      1,7296
 
 1,7232    2,5306    2,1638     8       3 points
 
 0,50      0,75   2  2,1602
 1,25      0,85      1,7459
 3,86      2,19   1  2,1638
 2,11      4,65   3  2,1544
 1,17      2,01      0,7596
 3,19      1,63      1,7212
 
 1,7278    2,5298    2,1622     9       3 points
 
 0,50      0,75   1  2,1622
 1,25      0,85      1,7465
 3,86      2,19   2  2,1591
 2,11      4,65   3  2,1543
 1,17      2,01      0,7625
 3,19      1,63      1,7169
 
 1,7256    2,5266    2,1608    10       3 points
 
 0,50      0,75   2  2,1583
 1,25      0,85      1,7427
 3,86      2,19   1  2,1608
 2,11      4,65   3  2,1579
 1,17      2,01      0,7586
 3,19      1,63      1,7171
 
 1,7270    2,5264    2,1594    11       3 points
 
 0,50      0,75   2  2,1589
 1,25      0,85      1,7429
 3,86      2,19   1  2,1594
 2,11      4,65   3  2,1579
 1,17      2,01      0,7595
 3,19      1,63      1,7158
 
 1,7277    2,5262    2,1592    12       3 points
 
 0,50      0,75   1  2,1592
 1,25      0,85      1,7430
 3,86      2,19   2  2,1586
 2,11      4,65   3  2,1579
 1,17      2,01      0,7600
 3,19      1,63      1,7151
 
 1,7273    2,5257    2,1589    13       3 points
 
 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1589
 2,11      4,65   3  2,1585
 1,17      2,01      0,7593
 3,19      1,63      1,7151
 
 1,7275    2,5257    2,1587    14       3 points
 
 0,50      0,75   2  2,1587
 1,25      0,85      1,7424
 3,86      2,19   1  2,1587
 2,11      4,65   3  2,1585
 1,17      2,01      0,7594
 3,19      1,63      1,7149
 
 1,7276    2,5256    2,1587    15       3 points
 
 0,50      0,75   1  2,1587
 1,25      0,85      1,7424
 3,86      2,19   2  2,1586
 2,11      4,65   3  2,1585
 1,17      2,01      0,7595
 3,19      1,63      1,7148
 
 1,7276    2,5256    2,1587    16       3 points
 
 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1587
 2,11      4,65   3  2,1586
 1,17      2,01      0,7594
 3,19      1,63      1,7148
 
 1,7276    2,5255    2,1586    16       Solution a 3 points
 
 0,50      0,75   2  2,1586
 1,25      0,85      1,7423
 3,86      2,19   1  2,1586
 2,11      4,65   3  2,1586
 1,17      2,01      0,7594
 3,19      1,63      1,7148
 
CCCP Code Chalenge Code Project
Circle surounding dataset in plane
 
 2,6850    3,0700    3,1869     0       Solution a 2 points
 
 0,50      0,75   1  3,1869
 1,25      0,85      2,6434
 3,86      2,19      1,4680
 2,11      4,65      1,6814
 1,17      2,01      1,8490
 3,19      1,63      1,5260
 4,87      5,39   2  3,1869
 
CCCP Code Chalenge Code Project
Circle surounding dataset in plane
 
 7,7500    1,1900    9,2688     0       2 points
 
 0,50      0,75   1  7,2633
 1,25      0,85      6,5089
 3,86      2,19      4,0165
11,00      7,00      6,6572
 1,17      2,01      6,6309
15,00      1,63   2  7,2633
 4,87     10,00      9,2688
 
 7,7500    1,1900    9,2688     1       3 points
 
 0,50      0,75   2  7,2633
 1,25      0,85      6,5089
 3,86      2,19      4,0165
11,00      7,00      6,6572
 1,17      2,01      6,6309
15,00      1,63   3  7,2633
 4,87     10,00   1  9,2688
 
 7,4384    2,1431    8,2661     2       3 points
 
 0,50      0,75   3  7,0769
 1,25      0,85      6,3221
 3,86      2,19      3,5787
11,00      7,00      6,0228
 1,17      2,01      6,2698
15,00      1,63   2  7,5790
 4,87     10,00   1  8,2661
 
 7,2537    2,7082    7,8210     3       3 points
 
 0,50      0,75   3  7,0319
 1,25      0,85      6,2847
 3,86      2,19      3,4330
11,00      7,00      5,6968
 1,17      2,01      6,1236
15,00      1,63   1  7,8210
 4,87     10,00   2  7,6715
 
 7,6445    2,6538    7,8526     4       3 points
 
 0,50      0,75   3  7,3938
 1,25      0,85      6,6440
 3,86      2,19      3,8128
11,00      7,00      5,4908
 1,17      2,01      6,5064
15,00      1,63   2  7,4264
 4,87     10,00   1  7,8526
 
 7,5634    2,8685    7,6232     5       3 points
 
 0,50      0,75   3  7,3743
 1,25      0,85      6,6282
 3,86      2,19      3,7651
11,00      7,00      5,3740
 1,17      2,01      6,4508
15,00      1,63   2  7,5390
 4,87     10,00   1  7,6232
 
 7,5195    2,9849    7,6023     6       3 points
 
 0,50      0,75   3  7,3667
 1,25      0,85      6,6230
 3,86      2,19      3,7448
11,00      7,00      5,3137
 1,17      2,01      6,4239
15,00      1,63   1  7,6023
 4,87     10,00   2  7,4987
 
 7,6354    2,9639    7,5600     7       3 points
 
 0,50      0,75   3  7,4709
 1,25      0,85      6,7262
 3,86      2,19      3,8539
11,00      7,00      5,2546
 1,17      2,01      6,5354
15,00      1,63   2  7,4845
 4,87     10,00   1  7,5600
 
 7,6191    3,0054    7,5155     8       3 points
 
 0,50      0,75   3  7,4678
 1,25      0,85      6,7239
 3,86      2,19      3,8465
11,00      7,00      5,2333
 1,17      2,01      6,5254
15,00      1,63   2  7,5080
 4,87     10,00   1  7,5155
 
 7,6104    3,0276    7,5206     9       3 points
 
 0,50      0,75   3  7,4662
 1,25      0,85      6,7228
 3,86      2,19      3,8427
11,00      7,00      5,2221
 1,17      2,01      6,5202
15,00      1,63   1  7,5206
 4,87     10,00   2  7,4916
 
 7,6371    3,0225    7,5062    10       3 points
 
 0,50      0,75   3  7,4901
 1,25      0,85      6,7465
 3,86      2,19      3,8677
11,00      7,00      5,2086
 1,17      2,01      6,5459
15,00      1,63   2  7,4934
 4,87     10,00   1  7,5062
 
 7,6341    3,0299    7,4982    11       3 points
 
 0,50      0,75   3  7,4896
 1,25      0,85      6,7461
 3,86      2,19      3,8665
11,00      7,00      5,2048
 1,17      2,01      6,5441
15,00      1,63   2  7,4977
 4,87     10,00   1  7,4982
 
 7,6326    3,0339    7,5000    12       3 points
 
 0,50      0,75   3  7,4893
 1,25      0,85      6,7459
 3,86      2,19      3,8658
11,00      7,00      5,2028
 1,17      2,01      6,5432
15,00      1,63   1  7,5000
 4,87     10,00   2  7,4939
 
 7,6378    3,0329    7,4967    13       3 points
 
 0,50      0,75   3  7,4940
 1,25      0,85      6,7505
 3,86      2,19      3,8707
11,00      7,00      5,2002
 1,17      2,01      6,5482
15,00      1,63   2  7,4947
 4,87     10,00   1  7,4967
 
 7,6373    3,0342    7,4954    14       3 points
 
 0,50      0,75   3  7,4939
 1,25      0,85      6,7504
 3,86      2,19      3,8705
11,00      7,00      5,1996
 1,17      2,01      6,5479
15,00      1,63   1  7,4954
 4,87     10,00   2  7,4954
 
 7,6380    3,0340    7,4958    15       3 points
 
 0,50      0,75   3  7,4946
 1,25      0,85      6,7511
 3,86      2,19      3,8712
11,00      7,00      5,1992
 1,17      2,01      6,5486
15,00      1,63   2  7,4947
 4,87     10,00   1  7,4958
 
 7,6378    3,0346    7,4952    16       3 points
 
 0,50      0,75   3  7,4945
 1,25      0,85      6,7511
 3,86      2,19      3,8711
11,00      7,00      5,1989
 1,17      2,01      6,5485
15,00      1,63   2  7,4950
 4,87     10,00   1  7,4952
 
 7,6377    3,0349    7,4951    17       3 points
 
 0,50      0,75   3  7,4945
 1,25      0,85      6,7510
 3,86      2,19      3,8710
11,00      7,00      5,1988
 1,17      2,01      6,5484
15,00      1,63   1  7,4951
 4,87     10,00   2  7,4948
 
 7,6380    3,0348    7,4950    18       3 points
 
 0,50      0,75   3  7,4948
 1,25      0,85      6,7513
 3,86      2,19      3,8713
11,00      7,00      5,1986
 1,17      2,01      6,5487
15,00      1,63   2  7,4948
 4,87     10,00   1  7,4950
 
 7,6380    3,0350    7,4949    19       3 points
 
 0,50      0,75   3  7,4948
 1,25      0,85      6,7513
 3,86      2,19      3,8713
11,00      7,00      5,1985
 1,17      2,01      6,5487
15,00      1,63   2  7,4949
 4,87     10,00   1  7,4949
 
 7,6380    3,0350    7,4949    20       3 points
 
 0,50      0,75   3  7,4948
 1,25      0,85      6,7513
 3,86      2,19      3,8713
11,00      7,00      5,1985
 1,17      2,01      6,5487
15,00      1,63   1  7,4949
 4,87     10,00   2  7,4948
 
 7,6380    3,0350    7,4949    21       3 points
 
 0,50      0,75   3  7,4948
 1,25      0,85      6,7514
 3,86      2,19      3,8714
11,00      7,00      5,1985
 1,17      2,01      6,5487
15,00      1,63   2  7,4948
 4,87     10,00   1  7,4949
 
 7,6380    3,0350    7,4949    21       Solution a 3 points
 
 0,50      0,75   3  7,4948
 1,25      0,85      6,7514
 3,86      2,19      3,8714
11,00      7,00      5,1985
 1,17      2,01      6,5487
15,00      1,63   2  7,4949
 4,87     10,00   1  7,4949
  Permalink  
v5
Comments
Graeme_Grant 12-Jan-17 21:35pm
   
It has been over 20 years since I have programmed in Clipper and was curious to see how your formula worked, so I ported it to C#. The results I got were a little off:

[edit: corrected a minor error, outcome still incorrect]

-----------------------------------

bestx: 1.305
besty: 2.7
bestr: 2.605403
tours: 0

... Solution a 2 points:
(0.5, 0.75) 1 D: 2.109627
(1.25, 0.85) - D: 1.850817
(3.86, 2.19) - D: 2.605403
(2.11, 4.65) 2 D: 2.109627
(1.17, 2.01) - D: 0.7030826
(3.19, 1.63) - D: 2.167516

-----------------------------------

bestx: 2.685
besty: 3.07
bestr: 3.186946
tours: 0

... Solution a 2 points:
(0.5, 0.75) 1 D: 3.186946
(1.25, 0.85) - D: 2.643411
(3.86, 2.19) - D: 1.468
(2.11, 4.65) - D: 1.681376
(1.17, 2.01) - D: 1.849006
(3.19, 1.63) - D: 1.525983
(4.87, 5.39) 2 D: 3.186946

Are you seeing the same?
Graeme_Grant 12-Jan-17 22:13pm
   
Here is the converted C# code used:

using System;
using System.Collections.Generic;
 
namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(2.11f, 4.65f),
                new Point(1.17f, 2.01f),
                new Point(3.19f, 1.63f)
            });
 
            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(2.11f, 4.65f),
                new Point(1.17f, 2.01f),
                new Point(3.19f, 1.63f),
                new Point(4.87f, 5.39f)
            });
 
            CircleFit(new List<Point>()
            {
                new Point(0.5f, 0.75f),
                new Point(1.25f, 0.85f),
                new Point(3.86f, 2.19f),
                new Point(11f, 7f),
                new Point(1.17f, 2.01f),
                new Point(15f, 1.63f),
                new Point(4.87f, 10f)
            });
        }
 
        static int tours = 0;
        static int p1 = 0, p2 = 0, p3 = 0;
        static float d1 = 0, d2 = 0, d3 = 0;
        static List<float> dist;
        static float bestx;
        static float besty;
        static float bestr;
 
ppolymorphe 12-Jan-17 22:25pm
   
Nothing obvious.
Are you sure about the /2 ? shouldn't it be /2.0 ?
Graeme_Grant 12-Jan-17 22:33pm
   
Checked that and it makes no difference for the first test - variance is -6.29564762 for "if (bestr - d1 / 2 > 0.0001)". I haven't spent time looking into why. [edit] Second test passes. Only 3 points on the circle appear to fail (same with the 3rd test that I included.)
Graeme_Grant 12-Jan-17 22:17pm
   
        private static void CircleFit(List<Point> data)
        {
            string sol = "";
            dist = new List<float>();
 
            tours = 0;
            p1 = p2 = p3 = 0;
            d1 = d2 = d3 = 0;
 
            for (int scan1 = 0; scan1 < data.Count-1; scan1++)
            {
                for (int scan2 = scan1+1; scan2 < data.Count; scan2++)
                {
                    var tmp = (float)Math.Sqrt(Math.Pow(Math.Pow(data[scan1].X - data[scan2].X, 2) + Math.Pow(data[scan1].Y - data[scan2].Y, 2), 2));
                    if (tmp > d1)
                    {
                        p1 = scan1;
                        p2 = scan2;
                        d1 = tmp;
                    }
                }
            }
            bestx = (data[p1].X + data[p2].X) / 2;
            besty = (data[p1].Y + data[p2].Y) / 2;
            bestr = CalcRadius(data, bestx, besty);
 
            if (bestr - d1 / 2 > 0.0001)
            {
                sol = "3 points";
                while (true)
                {
                    tours++;
                    p1 = p2 = p3 = 0;
                    d1 = d2 = d3 = 0;
 
                    for (int scan = 0; scan < data.Count; scan++)
                    {
                        if (data[scan].X > d1)
                        {
                            p3 = p2;
                            d3 = d2;
                            p2 = p1;
                            d2 = d1;
                            p1 = scan;
                            d1 = dist[scan];
                        }
                        else if (dist[scan] > d2)
                        {
                            p3 = p2;
                            d3 = d2;
                            p2 = scan;
                            d2 = dist[scan];
                        }
                        else if (dist[scan] > d3)
                        {
                            p3 = scan;
                            d3 = dist[scan];
                        }
                    }
                    aff(sol, data);
                    bestx = bestx + (data[p1].X - bestx) * (d1 - d3) / d1 / 2;
                    besty = besty + (data[p1].Y - besty) * (d1 - d3) / d1 / 2;
                    bestr = CalcRadius(data, bestx, besty);
                    if (d1 - d3 < 0.0001) break;
                }
                sol = "Solution a 3 points";
            }
            else
            {
                sol = "Solution a 2 points";
            }
            aff(sol, data);
        }
 
Graeme_Grant 12-Jan-17 22:18pm
   
        class Point
        {
            public Point(float x, float y)
            {
                X = x;
                Y = y;
            }
            public float X { get; set; }
            public float Y { get; set; }
        }
 
        private static void aff(string sol, List<Point> data)
        {
            Console.WriteLine("-----------------------------------");
            Console.WriteLine("");
            Console.WriteLine($"bestx: {bestx}");
            Console.WriteLine($"besty: {besty}");
            Console.WriteLine($"bestr: {bestr}");
            Console.WriteLine($"tours: {tours}");
            Console.WriteLine("");
            Console.WriteLine($"...  {sol}: ");
 
            for (int i = 0; i < data.Count; i++)
            {
                Console.Write($"    ({data[i].X}, {data[i].Y})");
                if (i == p1) Console.Write(" 1");
                else if (i == p2) Console.Write(" 2");
                else if (i == p3) Console.Write(" 3");
                else Console.Write(" -");
                Console.WriteLine($"   D: {dist[i]}");
            }
            Console.WriteLine("");
            Console.ReadKey();
        }
 
        private static float CalcRadius(List<Point> data, float cx, float cy)
        {
            dist.Clear(); // reset before calc
            float cr = 0;
            for (int scan = 0; scan < data.Count; scan++)
            {
                dist.Add((float)Math.Sqrt(Math.Pow(cx - data[scan].X, 2) + Math.Pow(cy - data[scan].Y, 2)));
                if (cr < dist[scan])
                    cr = dist[scan];
            }
            return cr;
        }
    }
ppolymorphe 12-Jan-17 22:35pm
   
Is this dist.Add replacing values in dist ?
Graeme_Grant 12-Jan-17 22:41pm
   
Yes, just found that myself - my sincere apologies.

However after fixing, the 3rd test that I provided failed.

-----------------------------------

bestx: 7.75
besty: 1.19
bestr: 9.268792
tours: 0

... Solution a 2 points:
(0.5, 0.75) 1 D: 7.26334
(1.25, 0.85) - D: 6.508886
(3.86, 2.19) - D: 4.016479
(11, 7) - D: 6.657222
(1.17, 2.01) - D: 6.630898
(15, 1.63) 2 D: 7.26334
(4.87, 10) - D: 9.268792

Should be:

** TEST: 3 > Spread - 7 locations ....

RADIUS: 7.49485 Center: (7.638026,3.03503)

(0.5,0.75) is on the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(11,7) is inside the circle
(1.17,2.01) is inside the circle
(15,1.63) is on the circle
(4.87,10) is on the circle

--------------------------------------------------------

ppolymorphe 12-Jan-17 22:54pm
   
I get correct solution for set 3
Graeme_Grant 12-Jan-17 23:09pm
   
Your variable scope made it interesting to port but as far as I can see, the port to C# is now correct and am seeing the first and 3rd tests failing. Anyone else seeing the same?
ppolymorphe 12-Jan-17 22:48pm
   
I think the problem that you create an empty dist and then add values, but never remove previous values.
CalcRadius most remove old values from dist.
Graeme_Grant 12-Jan-17 22:53pm
   
That was corrected (see code above). Have you tried using the 3rd dataset provided with your Clipper version? [edit] I want to give it 5 stars if all tests pass.
ppolymorphe 12-Jan-17 23:01pm
   
Note that I use Windows incarnation of Clipper
I use xHabour, witch also provide a utility named xPrompt witch allow scripting.
Another incarnation look to have more activity lately is Harbour.
ppolymorphe 13-Jan-17 15:34pm
   
Have you seen my last update in solution ?
Have you found why your program go wrong ?
Graeme_Grant 13-Jan-17 15:44pm
   
Just saw your note now. No, have not had time to do further investigation. Just worked through the night (6:45am here now), quickly did the next challenge, and about to go to bed. Will check this again later today (Saturday).
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 11

Here's a naive (non-optimal) implementation in SQL. I don't do math without a really good reason. It is, at least, "the smallest circle I care to determine". At least one point from the set will be on the circle.

WITH [points] AS
(
  SELECT 0.50 [X] , 0.75 [Y]
  UNION ALL
  SELECT 1.25 [X] , 0.85 [Y]
  UNION ALL
  SELECT 3.86 [X] , 2.19 [Y]
  UNION ALL
  SELECT 2.11 [X] , 4.65 [Y]
  UNION ALL
  SELECT 1.17 [X] , 2.01 [Y]
  UNION ALL
  SELECT 3.19 [X] , 1.63 [Y]
)
SELECT A.[X] 
, A.[Y] 
, B.[Xmid]
, B.[Ymid]
, SQRT(POWER(A.[X]-B.[Xmid],2)+POWER(A.[Y]-B.[Ymid],2)) [Radius] 
FROM [points] A
CROSS JOIN (
  SELECT (MIN([X])+MAX([X]))/2.0 [Xmid] , (MIN([Y])+MAX([Y]))/2.0 [Ymid]
  FROM [points]
) B
ORDER BY [Radius] DESC
OFFSET 0 ROWS
FETCH FIRST 1 ROW ONLY


X    Y    Xmid     Ymid     Radius
0.50 0.75 2.180000 2.700000 2.5738881094562


(A man's gotta know his limitations.)
  Permalink  
v2
Comments
ppolymorphe 10-Jan-17 5:05am
   
Hi,
I fear your solution is wrong.
Circle center is {1.73, 2.53} and Radius is 2.16.
There is a minimum of 2 points on circle.
PIEBALDconsult 10-Jan-17 8:31am
   
I said "non-optimal", are any of the points outside the circle?
ppolymorphe 10-Jan-17 20:59pm
   
Ok
But is it a solution to the coding challenge ?
PIEBALDconsult 10-Jan-17 21:58pm
   
Yes, just not an optimal one, and I know it.
Chris Maunder 10-Jan-17 11:06am
   
Majestic in its awfulness.
Graeme_Grant 10-Jan-17 22:02pm
   
Nice attempt PIEBALDconsult. I have not run your code but looking at your formula, you won't get the correct smallest enclosing circle for these points: (0.5,0.75), (1.25,0.85), (3.86,2.19), (11,7), (1.17,2.01), (15,1.63), (4.87,10). You can check it with this spreadsheet[^]
PIEBALDconsult 10-Jan-17 22:04pm
   
That's because I didn't try very hard. This is outside my comfort zone.
Graeme_Grant 11-Jan-17 0:20am
   
Mine too but my son is a math geek, so team effort... Had fun learning Powershell & F#. Powershell I'll use a lot more now, but F# is another ballgame.
Maciej Los 11-Jan-17 15:45pm
   
I like it!
Stefan_Lang 16-Jan-17 1:55am
   
I like the idea of using a database engine to solve a math problem - after all, database engines are typically highly optimized. Although your solution doesn't provide the optimal solution, that is a problem of the algorithm you used, not a limitation of SQL. I wonder how well an optimal SQL solution would compare to a solution written in , say, C++, C# or similar.
PIEBALDconsult 16-Jan-17 16:52pm
   
Right. It seems this problem inherently lends itself to an iterative solution and SQL isn't really suited to that. A Recursive Common Table Expression might be required.
Stefan_Lang 17-Jan-17 1:49am
   
It should be doable without iteration, but my knowledge of SQL is severely lacking. Basically you need to select all pairs of points and all triplets of points and output the center and radius of the circles they define (for pairs, the center is the mid point), then pipeline the output into another select that for each circle prints the difference of point distance to the circle center (for all points) and circle radius, then select all the circles for which the maximum value of all point distances minus radius is 0, then select the circle with the smallest radius.

That's a limited amount of steps, so it should be doable.

[edit]of course, you need to specify a formula for directly calculating center and range of the circle defined by 3 points, which technically isn't hard, but may lead to some longish formulas. But I believe you can define functions in SQL for that kind of stuff?[/edit]
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 6

My solution is a no program solution: I simply used Excel and the Solver. Does it count ?

Principle:
For any center position, there is a circle that surround the dataset, its radius is the distance of farthest point.
I simply ask the Solver to move the circle center to minimize the radius.

Sheet:
A1= "Points X"
B1= "Points Y"
C1= "Distance"
D1= "Center X"
E1= "Center Y"
F1= "Radius"
F2= MAX(C2:C7)
 
Data set
A2=0.5
B2=0.75
C2=SQRT((D$2-A2)^2+(E$2-B2)^2)
...
 
Solver
Minimize: F2
Variables: D2:E2


Datset:
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }
Circle center: {1.73, 2.53}
Radius: 2.16
Note that 3 points in dataset are on the edge of circle.

Datset:
{ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39}}
Circle center: {2.69, 3.06}
Radius: 3.19
Note that 2 points in dataset are on the edge of circle.
  Permalink  
v8
Comments
Graeme_Grant 7-Jan-17 7:55am
   
Are you sure that your results are correct? The circle centre and radius can't be the same if the second dataset includes 4.87, 5.39. Point 4.87, 5.39 is in the corner of the bounding box and outside the circle. Here[^] is what it should look like.

** Update: check out my solution. I've added a link to an Excel spreadsheet with real time charting to visualize results.
ppolymorphe 7-Jan-17 10:26am
   
Ooops, too fast Copy/Paste operation for second dataset.
Good catch. Thank you for spoting.
I also have a graphic in my Excel sheet.
ppolymorphe 8-Jan-17 6:43am
   
Are you sure ?
I get 2 points on circle.
ppolymorphe 8-Jan-17 9:01am
   
Which problem have my solution ?
ppolymorphe 8-Jan-17 12:47pm
   
I am sorry, but I disagree , my solution to your corrected dataset have 3 points on circle, as you stated, but contrary to your picture.
Graeme_Grant 8-Jan-17 23:20pm
   
I have removed my comments after having a closer look at Excel Solver. The "Brute force" approach is an interesting one but it is doing the work for you, a bit like asking someone else to do your job/homework like Solution 4. ;)
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 5

Here is my C# (6.0) & VB.Net contribution that calculates both the center and radius of the smallest circle around a set of 2D points in 2 lines of code thanks to Linq!
Update: Just for fun, I've also added a C# 7.0 version using the new Tuples and it is super cool! Turns the C#6 spaghetti into something very easy to read. Can't wait for the official release!

Here is a solution with 5 versions in 4 different languages C# (6.0 & 7.0 versions), VB.Net, F#, & Powershell (F# & Powershell learned on the fly today!). :) Check calculation routine used is based on Arthur V. Ratz formula above...


class Program
{
    static void Main(string[] args)
    {
        var points = new List<Tuple<double, double>>()
    {
        new Tuple<double, double>(0.5, 0.75 ),
        new Tuple<double, double>(1.25, 0.85),
        new Tuple<double, double>(3.86, 2.19),
        new Tuple<double, double>(2.11, 4.65),
        new Tuple<double, double>(1.17, 2.01),
        new Tuple<double, double>(3.19, 1.63),
        new Tuple<double, double>(4.87,5.39)
    };
 
        var center = new Tuple<double, double>((points.Min(v => v.Item1) + points.Max(v => v.Item1)) / 2, (points.Min(v => v.Item2) + points.Max(v => v.Item2)) / 2);
 
        var radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5));
 
        var IsInCircle = new Func<Tuple<double, double>, bool>((pt) => Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2));
 
        Console.WriteLine($"RADIUS: {radius}  Center: ({center.Item1},{center.Item2})\r\n");
 
        foreach (var pt in points)
            Console.WriteLine($"({pt.Item1},{pt.Item2}) is {(IsInCircle(pt) ? "inside" : "outside")} the circle");
 
        Console.WriteLine("\r\n-- Press any key to exit --");
        Console.ReadKey();
    }
}

** UPDATE #2: Added C# 7.0 (RC) version
[note: requires VS 2017 RC & System.ValueTuple Nuget]

class Program
{
    static void Main(string[] args)
    {
        var points = new List<(double x, double y)>() { (0.5, 0.75), (1.25, 0.85), (3.86, 2.19), (2.11, 4.65), (1.17, 2.01), (3.19, 1.63), (4.87, 5.39) };
 
        (double x, double y) center = ((points.Min(v => v.x) + points.Max(v => v.x)) / 2, (points.Min(v => v.y) + points.Max(v => v.y)) / 2);
        double radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2)), 5));
 
        var IsInCircle = new Func<(double x, double y), bool>((pt) => Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2) <= Math.Pow(radius, 2));
 
        Console.WriteLine($"RADIUS: {radius}  Center: ({center.x},{center.y})\r\n");
 
        foreach (var pt in points)
            Console.WriteLine($"({pt.x},{pt.y}) is {(IsInCircle(pt) ? "inside" : "outside")} the circle");
 
        Console.WriteLine("\r\n-- Press any key to exit --");
        Console.ReadKey();
    }
}

** UPDATE #1: Added VB version

Sub Main()
 
    Dim points = New List(Of Tuple(Of Double, Double)) _
({
    New Tuple(Of Double, Double)(0.5, 0.75),
    New Tuple(Of Double, Double)(1.25, 0.85),
    New Tuple(Of Double, Double)(3.86, 2.19),
    New Tuple(Of Double, Double)(2.11, 4.65),
    New Tuple(Of Double, Double)(1.17, 2.01),
    New Tuple(Of Double, Double)(3.19, 1.63),
    New Tuple(Of Double, Double)(4.87, 5.39)
})
 
    Dim center As New Tuple(Of Double, Double)((points.Min(Function(v) v.Item1) + points.Max(Function(v) v.Item1)) / 2, (points.Min(Function(v) v.Item2) + points.Max(Function(v) v.Item2)) / 2)
 
    Dim radius = points.Max(Function(pt) Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5))
 
    Dim IsInCircle = New Func(Of Tuple(Of Double, Double), Boolean)(Function(pt) Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2))
 
    Console.WriteLine($"RADIUS: {radius}  Center: ({center.Item1},{center.Item2}){vbCrLf}")
 
    For Each pt In points
        Console.WriteLine($"({pt.Item1},{pt.Item2}) is {(If(IsInCircle(pt), "inside", "outside"))} the circle")
    Next
 
    Console.WriteLine($"{vbCrLf}-- Press any key to exit --")
    Console.ReadKey()
 
End Sub


** Update #4: F# version
[note: Thanks to Jon McKee, I took the plunge into F# and this is what resulted from my crash course in learning a second new language in a day. So please forgive me if there is a better way...]
open System
 
    let points = [(0.5, 0.75);
                  (1.25, 0.85); 
                  (3.86, 2.19); 
                  (2.11, 4.65); 
                  (1.17, 2.01); 
                  (3.19, 1.63); 
                  (4.87, 5.39)]
 
        let minx,miny,maxx,maxy = 
            points |> List.fold (fun (mx,my,Mx,My) (ax,ay) -> 
                 min mx ax, min my ay,
                 max Mx ax, max My ay) (999.0,999.0,-999.0,-999.0)
 
        let center:float*float = (minx + maxx) / 2.0, (miny + maxy) / 2.0
 
        let radius = 
            points |> List.fold (fun (mx) (ax, ay) ->
                max mx (System.Math.Round(sqrt((ax - fst center)**2.0 + (ay - snd center)**2.0), 5))) (0.0)
 
        let ReportResults =
           printfn "RADIUS %A  Center %A\r\n" radius center
           for pt in points do
                printfn "%A is %s the circle" pt (if ((fst pt - fst center)**2.0 + (snd pt - snd center)**2.0 <= radius**2.0) then "inside" else "outside")
 
[<EntryPoint>]
let main argv = 
 
    printfn"\r\n-- Press any key to exit --";
    Console.ReadKey() |> ignore;
    0

Outputs:
RADIUS: 3.18695  Center: (2.685,3.07)
 
(0.5,0.75) is inside the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(2.11,4.65) is inside the circle
(1.17,2.01) is inside the circle
(3.19,1.63) is inside the circle
(4.87,5.39) is inside the circle
 
-- Press any key to exit --


** Update #3: Powershell version
[note: This is my first attempt at Powershell, so please forgive me if there is a quicker way...]

$points = [System.Tuple]::Create(0.5, 0.75),
          [System.Tuple]::Create(1.25, 0.85),
          [System.Tuple]::Create(3.86, 2.19),
          [System.Tuple]::Create(2.11, 4.65),
          [System.Tuple]::Create(1.17, 2.01),
          [System.Tuple]::Create(3.19, 1.63),
          [System.Tuple]::Create(4.87, 5.39)
$minX = 9999.0; $minY = 9999.0
 
$points | foreach {$minX=[math]::Min($minX, $_.item1); $maxX=[math]::Max($maxX, $_.item1); $minY=[math]::Min($minY, $_.item2); $maxY=[math]::Max($maxY, $_.item2)}
 
$center = [System.Tuple]::Create(($minX + $maxX) / 2,($minY + $maxY) / 2)
 
$points | foreach {$radius=[math]::Max($radius, [math]::round([math]::sqrt([math]::pow($_.item1 - $center.item1,2)+[math]::pow($_.item2 - $center.item2,2)),5))}
 
echo "RADIUS: $radius  Center: $center"
$points | foreach {$t=[math]::pow($_.item1-$center.item1,2)+[math]::pow($_.item2-$center.item2,2) -le [math]::pow($r,2); if($t) {$p="inside"} else {$p="outside"}; echo "$_ is $p the circle"}

Outputs:
RADIUS: 3.18695  Center: (2.685, 3.07)
(0.5, 0.75) is inside the circle
(1.25, 0.85) is inside the circle
(3.86, 2.19) is inside the circle
(2.11, 4.65) is inside the circle
(1.17, 2.01) is inside the circle
(3.19, 1.63) is inside the circle
(4.87, 5.39) is inside the circle


** UPDATE 5: Excel version with plot chart to visualize results
Here is a link to the spreadsheet[^] where you can test and visualize the formulas used in the above solutions.
  Permalink  
v19
Comments
Jon McKee 6-Jan-17 23:54pm
   
Oooo, do an F# version next! =D (just a jest =P)
Graeme_Grant 7-Jan-17 0:00am
   
Lmao! Thanks for the suggestion... I did think about it but don't really have the time to wrap my head around F# atm... :)
Jon McKee 7-Jan-17 0:04am
   
You've got another week, no excuses! Lol =)
Graeme_Grant 7-Jan-17 0:05am
   
I'm working on a very large project ATM... Maybe I can find some time to learn Typescript... :)
Jon McKee 7-Jan-17 0:11am
   
Best of luck on the project! I've been meaning to learn Powershell since I've heard it's basically Batch++ so that version is very interesting to me =)
Graeme_Grant 7-Jan-17 0:41am
   
I was the same until today ... I have found it to be super powerful and can't wait to spend more time with it. :)
Graeme_Grant 7-Jan-17 1:55am
   
Bit the bullet and did a F# version just for you. Was a bit of a challenge but accepted and done. ;)
Graeme_Grant 7-Jan-17 4:32am
   
Here is an Excel version too... Screenshot of formulas & output[^]

** Update: I've posted a link to the updated spreadsheet where you can play with the numbers and see the results visually charted in real time. Enjoy! :)
Arthur V. Ratz 8-Jan-17 3:12am
   
I'm afraid that your solution has the number of disadvantages: the first one is that it allows to find just one circle, and another one is that any points from the dataset should *NOT* reside within the border of a circle, which you'll never achieve by using your algorithm. The "geometric mean" formula that your algorithm relies on doesn't allow to find the desired approximation and thus it's impossible to find an appropriate radius of a circle that encloses all points inside and *NOT* at its border.

I've recently made some improvement to my code, so it always allows to find a circle that surrounds all points in the dataset. The correct value of radius is *NOT* 3.18695, *BUT* r = 3.30, to enclose all points and that's the best approximation. I'm very sorry, but my vote is 3 on both of your solutions 5 and 7. Thanks for reading my comment.
Graeme_Grant 8-Jan-17 3:18am
   
Yes, this solution doesn't satisfy all datasets but I think that you missed a point of the challenge "The circle may intersect points in the set". So the border is allowed.

Solution 7 is a more accurate version that does not have a margin of error found in this solution.
Arthur V. Ratz 8-Jan-17 3:23am
   
No, I think that the border is not allowed, because the points that reside on the border don't lie within the area enclosed by a circle. The belonging of such points to this area is in question.
Arthur V. Ratz 8-Jan-17 3:27am
   
And also, see my plot diagram that illustrates the correct solution of this problem: http://imgur.com/a/Oo0ah
Graeme_Grant 8-Jan-17 3:35am
   
Please take the time to re-read the challenge. Very much allowed.
Arthur V. Ratz 8-Jan-17 3:38am
   
I'm sorry, you're right since "The circle may intersect points in the set."...
Graeme_Grant 8-Jan-17 3:44am
   
If you are going to judge my solutions with a rating of 3, then all other solutions that make the same assumption as myself should be rated the same by yourself and not just mine. Thank you.
Graeme_Grant 8-Jan-17 3:58am
   
Solution 7 correctly gives the smallest circle for all datasets applied to it. Deserves better than a "3". I believe, from my own testing, it is the only solution that currently does. I guess that you can say thatI am a little biased. ;)
Graeme_Grant 8-Jan-17 3:44am
   
The Challenge states: "determine the centre and radius of the smallest circle" and "The circle may intersect points in the set". The challenge is a singular and not a plural request and intersection is allowed.

A circle by nature has a fixed radius, so for 2 points that intersect anywhere on the diameter can only be a single solution and not multiple as you suggest.

"The devil is in the details..."
Arthur V. Ratz 8-Jan-17 3:48am
   
Why do you think that multiple solutions cannot be ???
All solutions produced by my code are very close to one another and can be considered to be a single solution.
Graeme_Grant 8-Jan-17 3:51am
   
It suggests that your margin of error is very large. As stated above, circles have a fixed radius, so only a single enclosing smallest circle, is valid. IE: you can rotate the circle, but the radius and center remain the same. :)

Different story if we were asked to use ovals....
Arthur V. Ratz 8-Jan-17 4:01am
   
My margin of error is not very large, since you scarcely could find a circle with a smaller radius rather than the one shown in here: http://imgur.com/a/Oo0ah, having a radius 3.3.

And as you might noticed that all those circles in my resulting set having the same radius 3.3, which is definitely fixed.

About ellipses, we just don't discuss it.
Graeme_Grant 8-Jan-17 4:11am
   
Yes, but your multi-circle assumption is to not intersect any points which is not a valid assumption based on the conditions set for the challenge.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

Hi, Chris. Here's my solution to the code challenge problem:

<pre>#include <cmath>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef struct tagPoint
{
	double x;
	double y;
} PT;
 
typedef struct tagCircle
{
	double coord_x;
	double coord_y;
	double radius;
} CR;
 
const double precision_r = 0.1;
const double precision_pt = 0.01;
const double dim_x = 10, dim_y = 10;
 
std::vector<PT> points = { { 0.5, 0.75 }, { 1.25, 0.85 }, \
	{ 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } };
 
int main(int argc, char* argv[])
{
	double radius_min = -1;
	double radius = precision_r;
	clock_t time_start = std::clock();
	while (radius < dim_x && radius < dim_y)
	{
		for (double coord_x = 0; coord_x < dim_x; coord_x += precision_pt)
			for (double coord_y = 0; coord_y < dim_y; coord_y += precision_pt)
			{
				bool inside = true;
				for (auto it = points.begin(); it != points.end() && inside; it++)
					inside = ((std::pow(it->x - coord_x, 2.0) + \
						std::pow(it->y - coord_y, 2.0)) >= std::pow(radius, 2.0)) ? 0 : 1;
 
				if (inside == true)
				{
					if ((radius < radius_min) || (radius_min == -1))
						radius_min = radius;
				}
			}
	
		radius += precision_r;
	}
 
	printf("radius_min = %f\n", radius_min);
 
	std::vector<CR> circles;
	for (double coord_x = 0; coord_x < dim_x; coord_x += precision_pt)
		for (double coord_y = 0; coord_y < dim_y; coord_y += precision_pt)
		{
			bool inside = true;
			for (auto it = points.begin(); it != points.end() && inside; it++)
				inside = ((std::pow(it->x - coord_x, 2.0) + \
					std::pow(it->y - coord_y, 2.0)) >= std::pow(radius_min, 2.0)) ? 0 : 1;
 
			if (inside == true)
			{
				CR circle = { 0, 0, 0 };
				circle.radius = radius_min;
				circle.coord_x = coord_x; circle.coord_y = coord_y;
				circles.push_back(circle);
			}
		}
 

	for (auto it = circles.begin(); it != circles.end(); it++)
		if (it->coord_x > 0 && it->coord_y > 0 && it->radius == radius_min)
		{
			bool inside = true;
			for (auto it2 = points.begin(); it2 != points.end() && inside; it2++)
				inside = ((std::pow(it2->x - it->coord_x, 2.0) + \
					std::pow(it2->y - it->coord_y, 2.0)) >= std::pow(radius_min, 2.0)) ? 0 : 1;
 
			std::cout << "coord_x = " << it->coord_x << " " << "coord_y = " << it->coord_y << " " << "radius = " << it->radius;
			std::cout << " check..." << ((inside == true) ? "okey" : "wrong") << endl;
		}
 
	double w_time = (std::clock() - time_start) / (double)CLOCKS_PER_SEC;
 
	std::cout << "Time Elapsed: " << w_time << endl;
	std::cin.get();
 
    return 0;
}


Note: The following problem has the number of solutions and not only one (e.g. multiple circles with the minima radius can enclose all those points):

radius_min = 2.200000
coord_x = 1.69 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.69 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.7 coord_y = 2.59 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.71 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.72 coord_y = 2.58 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.73 coord_y = 2.57 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.74 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.75 coord_y = 2.56 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.76 coord_y = 2.55 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.77 coord_y = 2.54 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.78 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.79 coord_y = 2.53 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.8 coord_y = 2.52 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.81 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.82 coord_y = 2.51 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.83 coord_y = 2.5 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.84 coord_y = 2.49 radius = 2.2 check...okey
coord_x = 1.85 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.85 coord_y = 2.48 radius = 2.2 check...okey
coord_x = 1.86 coord_y = 2.47 radius = 2.2 check...okey
coord_x = 1.87 coord_y = 2.47 radius = 2.2 check...okey
Time Elapsed: 70.419


The rest of possible solutions can be obtained by running my code. Thanks.

To avoid any doubts regarding of the correctness of my code as well as an unnecessary discussion if my code exactly solves this problem, I've decided to graphically interpret the results obtained by using my code. Here's the link: https://i.imgur.com/A4Ew6H3.png.

That's all.
  Permalink  
v10
Comments
ppolymorphe 6-Jan-17 6:02am
   
I fear your circle is wrong !
With your data set, I get center around (1.75,2.5) with radius around 2.2
Arthur V. Ratz 6-Jan-17 6:20am
   
Hi, ppolymorphe. I'm sorry, *BUT* I'm not understanding your comment: what does it mean that you get center "around" (1.75, 2.5) with radius "around" 2.2 ??? My code normally ensures that you find all circles with center in (coord_x; coord_y) and specific radius_min value enclosing all those points in my dataset. Just to check if it's true you can take one or more points from the dataset, for example, (3.86; 2.19) point and coordinates of circle like (2.29; 2.98) with radius 3 taken from the output, and check if the following point is enclosed within a circle by using the following equation (x - coord_x)^2 + (y - coord_y)^2 <= radius^2. And obviously we get (3.86 - 2.29)^2 + (2.19 - 2.98)^2 <= 3^2, which is 1.57^2 + (-0.79)^2 <= 3^2 <= 9, 2.4649 + 0.6241 <= 9, 3.089 <= 9.
ppolymorphe 6-Jan-17 6:46am
   
I solved the problem graphically, so the values are approximated.
Arthur V. Ratz 6-Jan-17 6:26am
   
ppolymorphe, if you've got more questions, just post your comment, so I'm happy to answer your questions.
Ralf Meier 6-Jan-17 6:57am
   
I entered your values into my calculation - I don't agree exactly with ppolymorphe but also my values are quiet different to yours.
I got a Center-Point at (2.18 , 2.7) and a radius of 2.573888 (with your Points)
Arthur V. Ratz 6-Jan-17 7:03am
   
But, what particular points from the dataset: { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }; you've actually taken for this test. In your comment, you provided only central points of a circle and radius. If you take any point from the dataset it should exactly work. The example of computation I've already posted as the reply to ppolymorphe's comment (see. above).
Arthur V. Ratz 6-Jan-17 7:08am
   
Here's a quick steps for testing the sets of circle's central points and radiuses from the output that should enclose all of the points in the dataset ( { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } } ):

1) Take an arbitrary point from the dataset, for example (3.86; 2.19);
2) Take any of central points and radiuses provided in the output of my code, for example a circle at (2.29; 2.98) with radius 3;
3) Perform computation by using the following formula to determine if a point taken from the dataset at step 1 is enclosed within the specified circle with coordinates and radius taken at step 2:

(3.86 - 2.29)^2 + (2.19 - 2.98)^2 <= 3^2, which is 1.57^2 + (-0.79)^2 <= 3^2 <= 9, 2.4649 + 0.6241 <= 9, 3.089 <= 9.

And at now, don't you still understand my idea of how to solve this particular problem ??
ppolymorphe 6-Jan-17 7:30am
   
Hi Arthur,
Having all points inside of circle is only a part of conditions.
If you have at least 2 circles that surround all points, there is another circle with smaller radius that will surround all points too.
Arthur V. Ratz 6-Jan-17 7:34am
   
Hi ppolymorphe, Who told you that "If you have at least 2 circles that surround all points, there is another circle with smaller radius that will surround all points too...". - from my position it's simply not correct, though. The smaller circle enclosing all points might or might *NOT* exist.
ppolymorphe 7-Jan-17 4:14am
   
That is geometry.
Arthur V. Ratz 6-Jan-17 7:48am
   
And also, let me tell you what exactly my code does: it's simply aiming to iteratively find those coordinates and those radius values by using which we can draw a circle (not ellipse) surrounding all points in the dataset. This is typically done by using circle equation to test if a certain point belongs to a certain circle region with specific coordinates and radius. If we apply those values of a point coordinates, a circle coordinates and radius to the circle equation which is (x - coord_x)^2 + (y - coord_y)^2 <= R^2 and the condition is true, then we simply consider that point (x;y) is surrounded by the circle with coordinates (coord_x; coord_y) with radius equal to 3.

Isn't it clear ??
ppolymorphe 7-Jan-17 4:21am
   
My point was not to say that you have points outside of circle.
My point was to spot that the circle is not the smallest.
In your picture, move a center to {1.73,2.53} and you will see that there is a large margin around the dataset if radius is 3 and that it can be reduced.

By the way, thanks for providing a dataset.
Arthur V. Ratz 7-Jan-17 4:29am
   
ppolymorphe, thanks for your comment. To obtain the circle with smallest radius, just reduce the radius precision_r to 0.01 and gradually after the code execution you'll get a circle with smaller radius surrounding those points. Thanks.
ppolymorphe 7-Jan-17 4:46am
   
As the radius reduce, you will see that the number of possibles circles will reduce until 1 remain.
Arthur V. Ratz 7-Jan-17 4:57am
   
I'm sorry you actually should increase the precision by reducing the parameter precision_r by assigning it 0.01. This will actually give more results including circles with the actually smallest radius possible.

I'm just working to improve my code so it can produce a larger output dataset when the radius precision is increased to 0.01.
Arthur V. Ratz 7-Jan-17 5:31am
   
Thanks, ppolymorphe for the clarification. I've re-mastered my code and now it's obvious that the smallest radius for this dataset is 2.2.
Kornfeld Eliyahu Peter 9-Jan-17 4:02am
   
Note: The following problem has the number of solutions and not only one (e.g. multiple circles with the minima radius can enclose all those points):
NO! The geometrical problem of minimal circle has only one solution...
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

Here is my Solution in VB :

My Approach works like this :
- find the outer limit-Position as a surrounding rectangle
- find the center-Point of this rectangle
- now calculate the diagonal line from this center-point to each given point (
Hypothenuse 
of a Triangle) - the longest Hypothenuse gives the minimum radius for the surrounding circle

Module Calculate_Points
 
    Dim myPoints As PointF() = {New PointF(1, 1), New PointF(3, 7), New PointF(5, 2), New PointF(-3, -2), New PointF(5, 5), New PointF(2, 2)}
    Dim myPoints2 As PointF() = {New PointF(0, 0), New PointF(10, 0), New PointF(0, 10), New PointF(10, 10), New PointF(5, 5), New PointF(2, 2)}
 
    Function GetSurroundingRadius(xyPoints As PointF()) As Double
        Dim xMin As Double = xyPoints(0).X
        Dim yMin As Double = xyPoints(0).Y
        Dim xMax As Double = xyPoints(0).X
        Dim yMax As Double = xyPoints(0).Y
 
        For i As Integer = 1 To xyPoints.Length - 1
            xMin = Math.Min(xyPoints(i).X, xMin)
            xMax = Math.Max(xyPoints(i).X, xMax)
            yMin = Math.Min(xyPoints(i).Y, yMin)
            yMax = Math.Max(xyPoints(i).Y, yMax)
        Next
 
        Dim myWidth As Double = xMax - xMin
        Dim myHeight As Double = yMax - yMin
        Dim myCenter As New PointF(myWidth / 2 + xMin, myHeight / 2 + yMin)
 
        Dim myRadius As Double = 0.0
 
        Dim AK As Double = 0.0
        Dim GK As Double = 0.0
        Dim Hyp As Double = 0.0
 
        For i As Integer = 0 To xyPoints.Length - 1
            GK = Math.Abs(myCenter.Y - xyPoints(i).Y)
            AK = Math.Abs(myCenter.X - xyPoints(i).X)
            Hyp = Math.Sqrt(GK ^ 2 + AK ^ 2)
            myRadius = Math.Max(Hyp, myRadius)
        Next
 
        Return myRadius
    End Function
 
    Sub Test()
        Dim r As Single = GetSurroundingRadius(myPoints2)
        Dim a = 1
    End Sub
 
End Module


I tried to make it simple ... ;-)
  Permalink  
v3
Comments
tom1443 9-Jan-17 10:40am
   
I think you are close. The intersection of the diagonals of the bounding rectangle does locate the center of the points. But you need to calculate the distance from that center to every point using the distance formula and save the longest as the circle radius. Making the circle radius half the longest diagonal makes a circle that would be too big.
Ralf Meier 11-Jan-17 4:25am
   
Thanks for your reply ...
Haven't you seen the last part of my code, where I calculate the Hypothenuse (or let's the the used radius) from the center-Point to each given point. The longest Hypothenuse gives the real radius ...
Graeme_Grant 11-Jan-17 7:06am
   
Are you aware that for the code above: 1. only returns a radius and no center point for the smallest circle; 2. your first dataset returns an incorrect radius 6.02079725, not 5.830952; 3. the 2nd (box) dataset passes?
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 3

  1. We're trying to find the smallest bounding circle of an arbitrary number of points on a two dimensional plane.
  2. The two points that are farthest out from the center of the circle must be on the circumference of the circle itself.
  3. This means that the radius of the circle is half of the distance between the points that are farthest from each other.
  4. And that means that the centre of the circle is also the centre of this line that connects the two points farthest from each other.


#include "stdafx.h"
 
#include <iostream>
#include <cmath>
#include <unordered_set>
 
using namespace std;
 
class point
{
public:
	double x, y;
	point(std::unordered_set<double,double>::const_iterator &it){}
	point(double d1 =0.0, double d2=0.0) : x(d1), y(d2) {};
	point(const point& ref) :x(ref.x), y(ref.y) {}
};
 
bool operator==(const point& lhs, const point& rhs)
{
	return (lhs.x == rhs.x && lhs.y == rhs.y);
}
 
namespace std
{
	template <> struct std::hash<point>
	{
		size_t operator()(point const & x) const noexcept
		{
			return static_cast<size_t>((15 + std::hash<double>()(x.x) * 15 + std::hash<double>()(x.y)));
		}
	};
}
 
double dist(const point &p1, const point &p2) noexcept //computes the distance between two 2d points.
{
	return std::sqrt( fabs(p1.x - p2.x) * fabs(p1.x - p2.x) + fabs(p1.y - p2.y) * fabs(p1.y - p2.y)	);
}
 
int main()
{
	unordered_set<point> points{ point(0, 0), point(4, 4) };
	double result = 0.0, temp = 0.0;
	point centre;
 
	for (auto it = points.begin(); it != points.end(); it++)
	{
		for (auto it2 = it; it2 != points.end(); it2++)
		{
			temp = dist(*it, *it2);
			if (temp > result)
			{
				centre.x = fabs((it->x + it2->x) / 2);
				centre.y = fabs((it->x + it2->y) / 2);
				result = temp;
			}
		}
	}
 
	std::cout << "Radius of minimum bounding circle = " << result / 2 << endl;
	std::cout << "Centre of circle = " << centre.x << "," << centre.y << endl;
	return 0;
}
  Permalink  
v6
Comments
Rob Philpott 6-Jan-17 5:43am
   
Slightly bothered that I am concerning myself with this problem, but...

I'm fairly sure that assertions 3 & 4 are incorrect.

Cut a square in half diagonally to make a triangle, the farthest points are on the hypotenuse, so centre point would be half way along it. Draw a circle here r=h/2 and all 3 points touch it. Now edge the point of the triangle out a bit. It is outside the circle but doesn't affect that farthest points...
Rajesh R Subramanian 6-Jan-17 5:55am
   
Hi Rob, thanks for taking the time to comment. You could be 100% right here, but based on what I have understood of your comment, "edging the triangle out a bit" part. If the triangle is edged out, then the points have moved, so it would invalidate the calculation. By "edging" if you mean rotating on the axis of the centre point, then all the points that are already on the circumference would rotate ON the circumference of the circle. I also didn't mention in the original solution, but there could be more than two points on the circumference of the circle. However, I think that wouldn't affect the solution since the distance to that point from the centre will still be the same as what we've calculated.
Rob Philpott 6-Jan-17 6:16am
   
Ah, it'd be better if computers had pens than keyboards!

On the half square triangle which has all three points on the circle, move just the point not on the hypotenuse so its outside the circle. Other 2 points stay where they are. This small change won't affect the two points farthest from each other, but a circle centred half way between them no longer contains all 3 points.
Rajesh R Subramanian 6-Jan-17 6:29am
   
I think I now know what you're saying. :(

Now I'm having another think. Thanks for bringing this up, Rob. You're awesome!
Rob Philpott 6-Jan-17 6:35am
   
Yes, saying things are just wrong without offering any alternative solution and without troubling my own brain on how this might be solved makes me think I should move into management. Good luck!
Rajesh R Subramanian 6-Jan-17 6:14am
   
I took a right angled triangle as a test case, and wanted to verify that it works correctly. The co-ordinates are 0,0 and 4,4. The program output was: Radius of minimum bounding circle = 2.82843
Centre of circle = 2,2

I checked that with Wolfram Alpha and the results seem to be the same: https://www.wolframalpha.com/input/?i=distance+between+(2,2)+to+(0,0)
ppolymorphe 7-Jan-17 4:53am
   
I fear point 2 is also wrong. Depending on dataset, it is 2 or 3 points on the edge of circle.
Rajesh R Subramanian 7-Jan-17 19:56pm
   
Thanks for posting. You're 100% right. I figured that out after a bit of thinking following Rob's post. :-)
Stefan_Lang 17-Jan-17 3:03am
   
Assumptions 2, 3 and 4 are all incorrect: Consider a point set with 1000 points within the unit circle, and two points at (999.0, 0.0) and (1000.0, 0.0). The latter two points are the farthest away from the mean point, which is somewhere very close or even within the unit circle, but only the last point can be on the optimal circle boundary. Also, assumptions 3 and 4 fail miserably in this example.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 4

Obvious Solution:

Please sir, see my problem described at Coding challenge: smallest circle to surround a set of points[^]. I need code uregent for my project.

Sorry, couldn't resist.
  Permalink  
Comments
Tachyonx 6-Jan-17 6:26am
   
Ha ha ... this is a virtual solution thus using delegation,
valid approach, clear and simple ...
Chris Maunder 6-Jan-17 10:30am
   
You get half a point.
Jon McKee 6-Jan-17 14:13pm
   
Thank you for making me laugh so hard I got weird looks from people :thumbsup:
ppolymorphe 7-Jan-17 3:37am
   
We don't do your HomeWork ... :-)
Couldn't resist either.
Graeme_Grant 8-Jan-17 2:18am
   
It definitely felt like we were doing someone's homework...
ppolymorphe 8-Jan-17 6:26am
   
LOL
CPallini 9-Jan-17 6:49am
   
5.
Sorry, couldn't resist.
Graeme_Grant 10-Jan-17 20:18pm
   
A shame that as this is a "coding challenge" that "no code" & "humor only" does not qualify...
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 12

Here's a fairly compact C# console app that meets the requirements AFAIK.

The process:
1. Take a list of points and calculate the center.
2. Calculate the distance for each point from the center and choose the farthest point for the radius.

using System;
using System.Collections.Generic;
 
namespace MinimumBoundingCircle
{
    class Program
    {
        struct PointF
        {            
            public float X;
            public float Y;
        }
        static void Main(string[] args)
        {
            Console.Out.WriteLine("Enter a comma delimited list of X and Y values:");
            string[] inValues = Console.In.ReadLine().Split(',');
            var vals = new List<PointF>();
            for(int i = 0;i< inValues.Length;i+=2)
            {
                PointF point = new PointF();
                point.X = float.Parse(inValues[i]);
                point.Y = float.Parse(inValues[i + 1]);
                vals.Add(point);
            }
            var cent = GetCenter(vals.ToArray());
            var radius = GetBoundingRadius(vals.ToArray(), cent);
            Console.Out.WriteLine("CenterX: " + cent.X);
            Console.Out.WriteLine("CenterY: " + cent.Y);
            Console.Out.WriteLine("Radius: " + radius);
            Console.Out.WriteLine("Press enter key to exit...");
            Console.In.ReadLine();
        }
        //Calculates the center point of a collection of points using 
        //Addapted formula from here: http://www.batesville.k12.in.us/Physics/APPhyNet/Dynamics/Center%20of%20Mass/2D_1.html
        static PointF GetCenter(PointF[] points)
        {
            float xSum = 0;
            float ySum = 0;
            foreach (PointF p in points)
            {
                xSum += p.X;
                ySum += p.Y;
            }
            return new PointF() { X = xSum / points.Length, Y = ySum / points.Length };
        }
        //Gets the bounding radius by checking for max distance from center for each point
        //Reference: http://math.info/Algebra/Distance_Cartesian_Plane/
        static float GetBoundingRadius(PointF[] points, PointF center)
        {
            float distance = 0.0f;
            foreach (PointF p in points)
            {
                float xDiffsSquared = 0;
                float yDiffsSquared = 0;
                var xDiff = center.X - p.X;
                var yDiff = center.Y - p.Y;
                xDiffsSquared = (xDiff * xDiff);
                yDiffsSquared = (yDiff * yDiff);
                float newDist = (float)Math.Sqrt(xDiffsSquared + yDiffsSquared);
                if (newDist > distance)
                {
                    distance = newDist;
                }
 
            }
            return distance;
        }
    }
}

Sample program output:
Enter a comma delimited list of X and Y values:
2,3,1,2.3,7.2,5.8,10.5,9.6,-5,10,3.2,1.3
CenterX: 3.15
CenterY: 5.333333
Radius: 9.3915
Press any key to exit...
  Permalink  
Comments
ppolymorphe 10-Jan-17 19:01pm
   
Looks like you need to refine your solution.
The center of circle is not at mean of all points. Adding points inside the circle do not change the center.
For your dataset, smallest circle center is {2.73,9.06} and radius is 7.79
Graeme_Grant 10-Jan-17 20:09pm
   
Agreed, requires more work.

Use this spreadsheet[^] to enter and see if your points & results pass.
Rick Shaub 11-Jan-17 10:47am
   
Thanks for the feedback guys. I underestimated the complexity of this problem. I'll leave this up as an example of a wrong approach.
Graeme_Grant 11-Jan-17 11:02am
   
Don't worry, my first attempt suffered from a similar problem. More complex than it looks. I left it up too and posted a second version.
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 16

GitHub - jm97/Circles: This project was created in response to the CodeProject coding challenge.[^]

Typical brute force calculation. Find all circles for all points based on duples and tuples. Then find all circles that contain all points, and give the trophy to the circle from the group with the smallest radius.

Bonus in the repo: Iterate over multiple random sets of points until a random set's smallest radius is less than an arbitrary threshold. So, for a cartesian grid, spanning -1000,-1000 to 1000,1000, generate random sets of arbitrary sample sizes until the radius of the smallest binding circle is less than, let's say, 50% of the maxiumum radius allowed by the cartesian grid.
  Permalink  
v2
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 9

Lemma: Suppose a circle in the Cartesian plane with center (a,b) and radius D. Consider a point (x,y) which is outside that circle. Then the distance between (a,b) and (x,y) is greater than D.

Assume the (x,y) values of the points are given. It is easy (see below) to write code to discover two points (a,b) and (c,d) such that the distance D between them is less than or equal to the distance between any other pair of points. By the above lemma, a circle centered on (a,b) with radius D encloses all the points (x,y). (Some may lie on the circumference.)

So the required program is simply to set up a 2-d matrix whose values are the distances between the points, then scan this to find two points with minimum distance. So easy that the code is not worth writing explicitly.
  Permalink  
Comments
ppolymorphe 9-Jan-17 12:26pm
   
The question is about showing a program (or at least a procedure) that solve the problem. Saying it is easy is not an answer.
Note: your solution is wrong: finding 2 points with minimum distance do not solve the problem and do not help finding the circle center.
pwasser 9-Jan-17 18:48pm
   
The problem is not to find any circle enclosing the data. That is child's play for which your proposal is the evidence. The problem is to find the smallest circle.
Member 12941311 9-Jan-17 19:20pm
   
Apologies. I realized later that my 'solution' was at best an initial approach, not a solution. I'll give it further thought. I wonder, however, whether an analytic solution is possible, or only a computational solution.
ppolymorphe 9-Jan-17 20:30pm
   
Use the Reply button on right of member name to answer a comment.
Advantage: the member is noticed.
Member 12941311 11-Jan-17 7:49am
   
Better minds than mine have come up with a couple of algorithmic (and thus computational) solutions which solve the problem in linear time (i.e. a linear function of the number of points). See https://en.m.wikipedia.org/wiki/Smallest-circle_problem

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy |
Web04 | 2.8.170915.1 | Last Updated 15 Jan 2017
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100