Click here to Skip to main content
15,867,308 members
Please Sign up or sign in to vote.
5.00/5 (6 votes)
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
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:
[no name] 6-Jan-17 12:13pm    
"Or an interesting use of a language": What do you think about Schwizerdütsch? Swiss German - Wikipedia[^]

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

C#
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
VB
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
PowerShell
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.
 
Share this answer
 
v10
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()
 
Share this answer
 
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:
C++
#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:
C++
#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:
C++
#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?
C++
#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;
}
 
Share this answer
 
v2
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
 
Share this answer
 
v10
Comments
Patrice T 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.
Patrice T 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
Maybe a bit late to the party, but I worked hard...
Coding Challenge: Smallest Circle Problem[^]
 
Share this answer
 
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! :)
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.
VB
*   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
 
Share this answer
 
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;

Patrice T 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);
        }

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.

SQL
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.)
 
Share this answer
 
v2
Comments
Patrice T 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?
Patrice T 10-Jan-17 20:59pm    
OkBut 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.
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.
 
Share this answer
 
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.
Patrice T 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.
Patrice T 8-Jan-17 6:43am    
Are you sure ?
I get 2 points on circle.
Patrice T 8-Jan-17 9:01am    
Which problem have my solution ?
Patrice T 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.
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...


C#
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]

C#
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

VB
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...]
F#
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...]

PowerShell
$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.
 
Share this answer
 
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 =)
Hi, Chris. Here's my solution to the code challenge problem:

C++
<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.
 
Share this answer
 
v10
Comments
Patrice T 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.
Patrice T 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)
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

VB
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 ... ;-)
 
Share this answer
 
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?
  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.


C++
#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;
}
 
Share this answer
 
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!
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.
 
Share this answer
 
Comments
peterkmx 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:
Patrice T 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...
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.

C#
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...
 
Share this answer
 
Comments
Patrice T 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.
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.
 
Share this answer
 
v2
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.
 
Share this answer
 
Comments
Patrice T 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.
[no name] 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.
Patrice T 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)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900