13,797,606 members
See more:
Today's challenge is a simple one: given an arbitrary set of points in the x,y plane, determine the centre and radius of the smallest circle that will enclose all points. The circle may intersect points in the set.

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

What I have tried:

To take some time off.

Last challenge[^]'s winner was Jon McKee, but only if he promises never to do that again. Jon: email Sean your contact details and something appropriate will be sent in return.
Posted 5-Jan-17 16:36pm
Updated 12-Jan-17 3:26am
v2
Jon McKee 6-Jan-17 0:07am

"Bonus points awarded for use of an interesting language." "only if he promises never to do that again." :( Ok... :P
Rajesh R Subramanian 6-Jan-17 5:08am

Mr Maunder, could you please fix the formatting in my solution post? :(
Ralf Meier 6-Jan-17 8:10am

You could do it by yourself.
Use the function "Improve Solution" and you are able to change what you have written ...
Rajesh R Subramanian 6-Jan-17 19:06pm

Ah, thank you. It's been so long since I've posted in the Q/A forums that I'd actually forgotten this. :laugh:
0x01AA 6-Jan-17 12:13pm

"Or an interesting use of a language": What do you think about Schwizerdütsch? Swiss German - Wikipedia[^]
PIEBALDconsult 6-Jan-17 15:31pm

Got sample data and test results?
Jon McKee 6-Jan-17 23:56pm

I think that's up to us this time around.
PIEBALDconsult 8-Jan-17 16:42pm

Alas.
Graeme_Grant 7-Jan-17 9:05am

I posted an excel spreadsheet where you can place points and visualize the results. Will that help you? ;)
Patrice T 10-Jan-17 19:13pm

Looks like official sample datasets would be a good idea to avoid wrong solutions.
Graeme_Grant 10-Jan-17 20:15pm

Tey can use this spreadsheet[^] to [manually] enter points & results and see they pass.
Patrice T 10-Jan-17 20:42pm

Yes, I know, but they don't.
See Solution 12
Graeme_Grant 10-Jan-17 20:57pm

I did see and commented. I shared the [manual] spreadsheet (with visual aid) as it appears they don't have a way of checking the results.
Kornfeld Eliyahu Peter 11-Jan-17 9:33am

It is acceptable to post an article as answer? I just made a lot of images and mathematical explanations I would like to share...
Chris Maunder 11-Jan-17 16:25pm

Absolutely

## Solution 7

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

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

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

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

Update: added VB.Net & Powershell versions

```using System;
using System.Collections.Generic;
using System.Linq;

namespace SmallestCircle
{
class Program
{
static void Main(string[] args)
{
var tests = new List<Tuple<string, List<Tuple<float, float>>>>()
{
new Tuple<string, List<Tuple<float, float>>>("Triangle", Test1()),
new Tuple<string, List<Tuple<float, float>>>("Box", Test2()),
new Tuple<string, List<Tuple<float, float>>>("Cluster", Test3()),
new Tuple<string, List<Tuple<float, float>>>("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";
});

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 --");
}

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;

pts.Remove(minPt);
ang1 = ang2;
}

// now fit smallest circle
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 (enclosesPts(tc, tr, region.Except(new List<Tuple<float, float>>() { pt1, pt2 })))
{
center = tc;
}
});
}

// 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 (enclosesPts(fc.Item2, fc.Item1, region.Except(new List<Tuple<float, float>>() { pt1, pt2, pt3 })))
{
center = fc.Item2;
}
}
});
}
}

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

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)

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++)

return points;
}
static Random random = new Random();
}
}```

** Update #2: VB.NET version
```Module Module1
Sub Main()

Dim tests = New List(Of Tuple(Of String, List(Of Tuple(Of Single, Single))))() From {
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Triangle", Test1()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Box", Test2()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Cluster", Test3()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Spread", Test4()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Circle", Test5()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Ellispe", Test6()),
New Tuple(Of String, List(Of Tuple(Of Single, Single)))("Random", Test7())
}

For i As Integer = 0 To tests.Count - 1
Dim points = tests(i).Item2

Console.WriteLine("--------------------------------------------------------")
Console.WriteLine(\$"** TEST: {i + 1} > {tests(i).Item1} - {points.Count} locations ...." & vbCr & vbLf)
If points.Count > 50 Then
Console.WriteLine("... this may take a little while...")
End If

Dim circle = SmallestCircle(points)
Dim circlePos = New Func(Of Tuple(Of Single, Single), String)(
Function(pt)
Dim cpt As Single = CSng(Math.Round(Math.Pow(pt.Item1 - circle.Item2.Item1, 2) + Math.Pow(pt.Item2 - circle.Item2.Item2, 2), 4))
Dim crd As Single = CSng(Math.Round(Math.Pow(circle.Item1, 2), 4))
Return If(cpt < crd, "inside", If(cpt = crd, "on", "outside"))

End Function)

Console.WriteLine(\$"RADIUS: {circle.Item1}  Center: ({circle.Item2.Item1},{circle.Item2.Item2})" & vbCr & vbLf)

For Each pt In points
Console.WriteLine(\$"({pt.Item1},{pt.Item2}) is {circlePos(pt)} the circle")
Next
Next
Console.WriteLine(vbCr & vbLf & "--------------------------------------------------------")
Console.WriteLine(\$"{tests.Count} Test run. Scroll up to see results.")
Console.WriteLine(vbCr & vbLf & "-- Press any key to exit --")

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

pts.Remove(minPt)
ang1 = ang2
End While

' now fit smallest circle
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 enclosesPts(tc, tr, region.Except(New List(Of Tuple(Of Single, Single))() From {pt1, pt2})) Then
center = tc
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 enclosesPts(fc.Item2, fc.Item1, region.Except(New List(Of Tuple(Of Single, Single))() From {pt1, pt2, pt3})) Then
center = fc.Item2
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

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
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
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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(10.11,12.58) is inside the circle
(3.81,1.28) is inside the circle
(0.22,7.51) is inside the circle
(9.69,9.01) is inside the circle
(17.69,8.97) is inside the circle
(12.43,7.64) is inside the circle
(0.56,10.34) is on the circle
(19.45,3.49) is on the circle
(13.65,13.74) is inside the circle
(13.53,2.39) is inside the circle

--------------------------------------------------------
7 Test run. Scroll up to see results.

-- Press any key to exit --```

I hope you all enjoy my tuple madness! :)

** Update #2: Powershell version
```using namespace System.Collections.Generic;

function Main
{
\$tests = [System.Tuple]::Create("Triangle", (Test1)),
[System.Tuple]::Create("Triangle", (Test2)),
[System.Tuple]::Create("Cluster", (Test3)),
[System.Tuple]::Create("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;

\$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; }

\$pts.Remove(\$minPt);
\$ang1 = \$ang2;
}

# now fit smallest circle
\$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);
\$ql = {\$region}.Invoke();
\$ql.Remove(\$pt1);
\$ql.Remove(\$pt2);
if (EnclosesPts(\$tc, \$tr, \$ql)) {
\$center = \$tc;
}
}
}
}

# 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);
\$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;
}
}
}
}
}

}

# 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);
}

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;

\$r = 3.187;
\$x = 2.685;
\$y = 3.07;

\$points = New-Object System.Collections.ArrayList;

for (\$i = 0; \$i -lt 360; \$i += \$step) {
}

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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(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 ....

(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.```
v10

## Solution 8

A really basic PowerShell solution:

```\$Coords = @(
@(100,50)
,@(50,50)
,@(10,30)
,@(100,30)
,@(102,90)
,@(80,60)
,@(40,110)
)

\$center = \$Coords | %{
\$a = \$_
\$Coords | %{
\$b = \$_
\$x = \$a[0] - \$b[0]
\$y = \$a[1] - \$b[1]
\$d = [Math]::Pow([Math]::Pow(\$x,2) + [Math]::Pow(\$y,2),1/2)
(new-object -TypeName PSObject -Property @{
Distance = \$d
X = (\$a[0] + \$b[0]) / 2.0
Y = (\$a[1] + \$b[1]) / 2.0
})
}
} | sort Distance -descending | select -First 1

#code to draw this
\$container = new-object Drawing.SolidBrush green
\$point = new-object Drawing.SolidBrush black
\$form = New-Object Windows.Forms.Form
\$formGraphics = \$form.createGraphics()
\$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()
```

## Solution 10

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

That's said we may do the following:

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

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

The code below will read space-delimited point data and output a space delimited circle center x y and circle radius:
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct point {
double  x, y;
} point_t;

static int err ( const char *msg, int code ) {
fputs ( msg, stderr );
return code;
}

static double distance ( point_t *p1, point_t *p2 ) {
double dx = p1->x - p2->x;
double dy = p1->y - p2->y;
return sqrt(dx*dx + dy*dy);
}

// this one will find a pair of points with a maximum
// distance between them, storing their indicies into
// i1 and i2 respectively
static double search_max_distance (
point_t *points,
size_t n,
size_t *_i,
size_t *_j
) {
size_t  i, j;
double  max_d = 0.0;
*_i = *_j = 0;
for ( i = 0; i < n; i++ )
for ( j = i+1; j < n; j++ ) {
double  d = distance(points+i, points+j);
if ( d > max_d ) {
max_d = d;
*_i = i;
*_j = j;
}
}
return max_d;
}

// circle through 3 points voodoo
// http://mathforum.org/library/drmath/view/54323.html
// returns radius of a circle, fills 'center' point
static double circle_vvv (
point_t *p1,
point_t *p2,
point_t *p3,
point_t *center,
double  line_threshold
) {
double x1=p1->x, x2=p2->x, x3=p3->x;
double y1=p1->y, y2=p2->y, y3=p3->y;
double temp = x2*x2 + y2*y2;
double bc = (x1*x1 + y1*y1 - temp) / 2.0;
double cd = (temp - x3*x3 - y3*y3) / 2.0;
double det = (x1-x2)*(y2-y3) - (x2-x3)*(y1-y2);
if ( fabs(det) < line_threshold ) {
// assume they are on a single line
return 0.0;
}
center->x = (bc*(y2-y3) - cd*(y1-y2)) / det;
center->y = ((x1-x2)*cd - (x2-x3)*bc) / det;
return distance(center, p1);
}

int main() {
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];
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;
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
min_center = center;
n_circles++;
}
}
if ( !n_circles ) return err ( "weird, no solution found", 3 );
success:
printf ( "% E  % E  % E\n", min_center.x, min_center.y, min_radius );
return 0;
}```

Given the brute-force flavor of the code above one can actually consider merging both phases into one search (where 2-point case is considered being a corner case for a 3-point candidate evaluation phase). Below code implements this 'single flow' idea (certainly being less efficient than the above version when it comes to finding a 2-point solution). Actually this one is the first I wrote for a challenge:
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct point {
double  x, y;
} point_t;

static int err ( const char *msg, int code ) {
fputs ( msg, stderr );
return code;
}

int main() {
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];
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;
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 ( l != n ) continue;
//fprintf ( stderr, "%E %E %E\n", center.x, center.y, radius );
min_center = center;
n_circles++;
}
}
}
}
if ( !n_circles ) return err ( "weird, no circle found", 3 );
success:
printf ( "% lE  % lE  % lE\n", min_center.x, min_center.y, min_radius );
return 0;
}```

Trust but verify, right? Both versions are a command line tools reading stdin and writing stdout. Here is a test bench using 'system()' call to invoke a 'circle' binary feeding it with random points, capturing its output and verifying if all generated points are within a circle. BTW, they are not because of precision issues related to using human-readable form of floating point number at both input and output compared to original full-precision data inside test program. What I did is that I measured how far an 'erroneous' points are outside of the circle compared to circle radius. Think of 1e-6 absolute error when circle radius is 4 or so. Looks like a rounding errors to me. Here's the test code:
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

static double frand_range(double range) {
return range * rand() / RAND_MAX - range / 2.0;
}

int main(int argc, char *argv[]) {
size_t  i, j, k, l;
double  range = 10.0;
double  threshold = 1e-5;
double  eps_min = 1e-6;

srand ( time(NULL) );
for ( i = 1; i <= 100; i++ ) {
size_t  n = i <= 3 ? 10 : 5;  // times
double  *x = malloc(sizeof*x * i);
double  *y = malloc(sizeof*y * i);
double  max_error = 0.0;
double  max_error_r = 0.0;
int retcode;
printf ( "%d:", i );
if ( !x || !y ) {
printf ( "one of those low memory days...\n" );
return 1;
}
for ( j = 0; j < n; j++ ) {
FILE    *fp = fopen ( "points", "wt" );
for ( k = 0; k < i; k++ ) {
x[k] = frand_range(range);
y[k] = frand_range(range);
fprintf ( fp, "% E  % E\n", x[k], y[k] );
}
fclose ( fp );
retcode = system ( "circle < points > c" );
printf ( ".%d", j+1 );
if ( retcode ) {
printf ( "retcode=%d\n", retcode );
return 2;
} else {
double  cx, cy, r, eps;
fp = fopen ( "c", "rt" );
if ( !fp || fscanf ( fp, " %lE %lE %lE", &cx, &cy, &r ) != 3 ) {
printf ( "why?!!\n" );
return 3;
}
fclose(fp);
eps = r * threshold;
if ( eps < eps_min ) eps = eps_min;
if ( r == 0.0 ) r = eps_min;
for ( l = 0; l < i; l++ ) {
double dx=cx-x[l];
double dy=cy-y[l];
double d = sqrt(dx*dx+dy*dy);
if ( d > r+eps ) {
printf ( "err=%lg d=%lg dx=%lg dy=%lg\n", d-r, d, dx, dy );
return 4;
}
if ( d > r ) {
double err = d-r;
if ( err > max_error ) {
max_error = err;
max_error_r = r;
}
}
}
}
}
free(x);
free(y);
printf ( " max_err=%lg (r=%lg)\n", max_error, max_error_r );
}
return 0;
}```

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

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

Below is a 40 LOC main() (with 80 chars per line limit obeyed) version of the mathematically correct solution that can detect errors and process corner cases same as above versions. My point is that despite its being raw it is still human-readable. What do you think?
```#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
struct dot {double x,y;} *dots=NULL;
size_t n=0;
double r=0.0;
for(n=0;;n++) {
if(!(n%1024)) if(!(dots=realloc(dots,sizeof*dots*(n+1024)))) return 1;
if(scanf(" %lE %lE", &dots[n].x, &dots[n].y)!=2) break;
}
if(!n) return 2;
else if (n>1) {
double x, y;
size_t i, j, k, l, cnum=0;
for(i=0;i<n;i++)
for (j=i+1;j<n;j++)
for (k=j;k<n;k++) {
double x1=dots[i].x, x2=dots[j].x, x3=dots[k].x;
double y1=dots[i].y, y2=dots[j].y, y3=dots[k].y;
double cx=(x1+x2)/2, cy=(y1+y2)/2;
double t=x2*x2+y2*y2, bc=(x1*x1+y1*y1-t)/2, cd=(t-x3*x3-y3*y3)/2;
double d=(x1-x2)*(y2-y3)-(x2-x3)*(y1-y2), rsq;
if(k!=j) {
if(d==0.0) continue;
cx=(bc*(y2-y3)-cd*(y1-y2))/d;
cy=((x1-x2)*cd-(x2-x3)*bc)/d;
}
rsq=(cx-x1)*(cx-x1)+(cy-y1)*(cy-y1);
for(l=0;l<n;l++) {
double dx=dots[l].x-cx, dy=dots[l].y-cy;
if(l==i || l==j || l==k) continue;
if(dx*dx+dy*dy > rsq) break;
}
if(l!=n || cnum && rsq>r*r) continue;
cnum++; r=sqrt(rsq); x=cx; y=cy;
}
if(!cnum) return 3;
dots[0].x=x; dots[0].y=y;
}
printf("% lE  % lE  % lE\n",dots[0].x, dots[0].y, r);
return 0;
}```
v2

## Solution 13

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

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

Now that I have got the plan, what tool should I use to implement it? I would like to have a tool that allows me to visualize the result in graphical points, lines, and circles with minimum code. Got it! R is the one! Here you are, my implementation in R:
```################################################################
# Coding challenge: smallest circle to surround a set of points
#      Submitted by Peter Leow the circle haunter
################################################################

require(plotrix)

# The set of x, y points in contention!
# Assume min 3 points
# Uncomment to try out different test sets
x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,1.7,2.2);
y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# x <- c(1.2,4.7,1.9,4.1,3.6,3.3,4.9,1.4,2.8,1.8,1.7,2.2);
# y <- c(3.1,4.7,2.0,3.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# x <- c(1.2,4.7,1.9,2.1,3.6,2.3,4.9,1.4,2.1,1.8,4.7,2.2);
# y <- c(3.1,4.7,2.0,5.5,3.5,4.6,1.5,3.2,2.3,2.3,3.5,2.4);

# Turn x, y into a list of point vectors
all_points <- mapply( c , x , y , SIMPLIFY = FALSE )

# Number of furthest pairs of points
num_furthest_pairs <- 3

# Vector of colors
colors = c("red","green","blue")

# Meet them in a plot
plot(x, y, main="Seeing is Believing in R by Peter Leow",
xlab="X", ylab="Y",
xlim=c(0, 10), ylim=c(0, 10))
axis(side=1, at=c(0:10))
axis(side=2, at=c(0:10))

# function to calculate Euclidean distance between 2 points
calEuclideanDistance <- function(point1, point2){

return (sqrt((point1[1]-point2[1])^2 + (point1[2]-point2[2])^2))

}

# function to find pairs of furthest points
findPairsOfFurthestPoints <- function(all_points){

furthest_pairs <- list()

for (n in 1:num_furthest_pairs){

furthest_distance <- 0

for (i in 1:(length(all_points)-1)) {

for (j in i+1:(length(all_points)-i)) {

b <- c(all_points[[i]], all_points[[j]])

if (n > 1 & Position(function(x) identical(x, b), furthest_pairs, nomatch = 0) > 0) next

distance <- calEuclideanDistance(all_points[[i]], all_points[[j]])

if (distance > furthest_distance) {

furthest_distance <- distance

furthest_pairs[[n]] <- c(all_points[[i]], all_points[[j]])

furthest_pairs[[n]]
}

}

}

}

return (furthest_pairs) # return a list containing num_furthest_pairs of pairs of furthest points in descending order
}

# Find 3 pairs of further points
pairsOfFurthestPoints <- findPairsOfFurthestPoints(all_points)

cat("The",num_furthest_pairs,"furthest pairs (x1 y1 x2 y2):\n")
cat("Pair #1 (Red)  :",pairsOfFurthestPoints[[1]],"\n") # first furthest pair
cat("Pair #2 (Green):",pairsOfFurthestPoints[[2]],"\n") # second furthest pair
cat("Pair #3 (Blue) :",pairsOfFurthestPoints[[3]],"\n") # third furthest pair

# Check out the pairs visually!
for (p in 1:num_furthest_pairs) {

points(pairsOfFurthestPoints[[p]][1],pairsOfFurthestPoints[[p]][2],cex=2,pch=4,col=colors[p])

points(pairsOfFurthestPoints[[p]][3],pairsOfFurthestPoints[[p]][4],cex=2,pch=4,col=colors[p])

center <- c(pairsOfFurthestPoints[[p]][1] + pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][2] + pairsOfFurthestPoints[[p]][4]) / 2

radius <- calEuclideanDistance(c(pairsOfFurthestPoints[[p]][1], pairsOfFurthestPoints[[p]][2]), c(pairsOfFurthestPoints[[p]][3], pairsOfFurthestPoints[[p]][4])) / 2

#points(center[1],center[2],cex=2,pch=18,col=colors[p])
}

# 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) {
}

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

center <- new_center

#print(center)

} # 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.

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
v10
Patrice T 11-Jan-17 10:11am

I fear your solution need some refinement.
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 ....

(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 ....

(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 ....

(1.2,3.1) is inside the circle
(4.7,4.7) is inside the circle
(1.9,2) is inside the circle
(2.1,5.5) is on the circle
(3.6,3.5) is inside the circle
(2.3,4.6) is inside the circle
(4.9,1.5) is on the circle
(1.4,3.2) is inside the circle
(2.1,2.3) is inside the circle
(1.8,2.3) is inside the circle
(4.7,3.5) is inside the circle
(2.2,2.4) is inside the circle
Peter Leow 11-Jan-17 11:19am

Graeme_Grant 11-Jan-17 11:24am

yes, I see. I was replying to you when you replied to ppolymorphe. :)

The solution that we used, in a nutshell, was to: find the outer max points, remove the inner points (not required), then find the best fit with the remaining points.
Peter Leow 11-Jan-17 11:30am

Yes. Thank you for trying out my code.
Graeme_Grant 11-Jan-17 11:36am

Looks good with the adjustment. :)

## Solution 14

Maybe a bit late to the party, but I worked hard...
Coding Challenge: Smallest Circle Problem[^]
v2
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 ....

(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

## Solution 15

My solution with a real program. Clipper language (mostly FoxPro)
The method:
1) find the farthest 2 points from each others.
2) try the 2 points on circle solution, center is in the middle of the 2 points.
3) if a point a farther than the radius, the 2 points solution don't work.
4) switch to 3 points on circle solution.
5) search 3 farthest points from center.
6) move center closer to farthest point.
7) repeat at 5 until 3 farthest points are same distance.
```*   CCCP Code Challenge Code Project
* Circle surounding dataset in plane
clear
CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } })

CircleFit({ { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 }, {4.87, 5.39} })

return

function Circlefit(data)
clear
@ 2, 0 say "CCCP Code Challenge Code Project"
@ 3, 0 say "Circle surrounding dataset in plane"
dist= array(len(data))

tours=0
* Solve 2 Points
* trouver les 2 points les + eloignes
d1= 0
p3= 0
for scan1=1 to len(data)-1
for scan2=scan1+1 to len(data)
tmp= sqrt((data[scan1,1]-data[scan2,1])^2+(data[scan1,2]-data[scan2,2])^2)
if tmp > d1
p1= scan1
p2= scan2
d1= tmp
endif
next
next
bestx= (data[p1,1]+ data[p2,1])/2
besty= (data[p1,2]+ data[p2,2])/2
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
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

*	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```
v5
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.  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;

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;
if (d1 - d3 < 0.0001) break;
}
sol = "Solution a 3 points";
}
else
{
sol = "Solution a 2 points";
}
aff(sol, data);
}

```
Graeme_Grant 12-Jan-17 22:18pm

```        class Point
{
public Point(float x, float y)
{
X = x;
Y = y;
}
public float X { get; set; }
public float Y { get; set; }
}

private static void aff(string sol, List<Point> data)
{
Console.WriteLine("-----------------------------------");
Console.WriteLine("");
Console.WriteLine(\$"bestx: {bestx}");
Console.WriteLine(\$"besty: {besty}");
Console.WriteLine(\$"bestr: {bestr}");
Console.WriteLine(\$"tours: {tours}");
Console.WriteLine("");
Console.WriteLine(\$"...  {sol}: ");

for (int i = 0; i < data.Count; i++)
{
Console.Write(\$"    ({data[i].X}, {data[i].Y})");
if (i == p1) Console.Write(" 1");
else if (i == p2) Console.Write(" 2");
else if (i == p3) Console.Write(" 3");
else Console.Write(" -");
Console.WriteLine(\$"   D: {dist[i]}");
}
Console.WriteLine("");
}

private static float CalcRadius(List<Point> data, float cx, float cy)
{
dist.Clear(); // reset before calc
float cr = 0;
for (int scan = 0; scan < data.Count; scan++)
{
dist.Add((float)Math.Sqrt(Math.Pow(cx - data[scan].X, 2) + Math.Pow(cy - data[scan].Y, 2)));
if (cr < dist[scan])
cr = dist[scan];
}
return cr;
}
}```
Patrice T 12-Jan-17 22:35pm

Is this dist.Add replacing values in dist ?
Graeme_Grant 12-Jan-17 22:41pm

Yes, just found that myself - my sincere apologies.

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

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

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

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

Should be:

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

(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

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

Patrice T 12-Jan-17 22:54pm

I get correct solution for set 3
Graeme_Grant 12-Jan-17 23:09pm

Your variable scope made it interesting to port but as far as I can see, the port to C# is now correct and am seeing the first and 3rd tests failing. Anyone else seeing the same?
Patrice T 12-Jan-17 22:48pm

I think the problem that you create an empty dist and then add values, but never remove previous values.
CalcRadius most remove old values from dist.
Graeme_Grant 12-Jan-17 22:53pm

That was corrected (see code above). Have you tried using the 3rd dataset provided with your Clipper version?  I want to give it 5 stars if all tests pass.
Patrice T 12-Jan-17 23:01pm

Note that I use Windows incarnation of Clipper
I use xHabour, witch also provide a utility named xPrompt witch allow scripting.
Another incarnation look to have more activity lately is Harbour.
Patrice T 13-Jan-17 15:34pm

Have you seen my last update in solution ?
Have you found why your program go wrong ?
Graeme_Grant 13-Jan-17 15:44pm

Just saw your note now. No, have not had time to do further investigation. Just worked through the night (6:45am here now), quickly did the next challenge, and about to go to bed. Will check this again later today (Saturday).

## Solution 11

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

```WITH [points] AS
(
SELECT 0.50 [X] , 0.75 [Y]
UNION ALL
SELECT 1.25 [X] , 0.85 [Y]
UNION ALL
SELECT 3.86 [X] , 2.19 [Y]
UNION ALL
SELECT 2.11 [X] , 4.65 [Y]
UNION ALL
SELECT 1.17 [X] , 2.01 [Y]
UNION ALL
SELECT 3.19 [X] , 1.63 [Y]
)
SELECT A.[X]
, A.[Y]
, B.[Xmid]
, B.[Ymid]
FROM [points] A
CROSS JOIN (
SELECT (MIN([X])+MAX([X]))/2.0 [Xmid] , (MIN([Y])+MAX([Y]))/2.0 [Ymid]
FROM [points]
) B
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.)
v2
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

Ok But is it a solution to the coding challenge ?
PIEBALDconsult 10-Jan-17 21:58pm

Yes, just not an optimal one, and I know it.
Chris Maunder 10-Jan-17 11:06am

Majestic in its awfulness.
Graeme_Grant 10-Jan-17 22:02pm

Nice attempt PIEBALDconsult. I have not run your code but looking at your formula, you won't get the correct smallest enclosing circle for these points: (0.5,0.75), (1.25,0.85), (3.86,2.19), (11,7), (1.17,2.01), (15,1.63), (4.87,10). You can check it with this spreadsheet[^]
PIEBALDconsult 10-Jan-17 22:04pm

That's because I didn't try very hard. This is outside my comfort zone.
Graeme_Grant 11-Jan-17 0:20am

Mine too but my son is a math geek, so team effort... Had fun learning Powershell & F#. Powershell I'll use a lot more now, but F# is another ballgame.
Maciej Los 11-Jan-17 15:45pm

I like it!
Stefan_Lang 16-Jan-17 1:55am

I like the idea of using a database engine to solve a math problem - after all, database engines are typically highly optimized. Although your solution doesn't provide the optimal solution, that is a problem of the algorithm you used, not a limitation of SQL. I wonder how well an optimal SQL solution would compare to a solution written in , say, C++, C# or similar.
PIEBALDconsult 16-Jan-17 16:52pm

Right. It seems this problem inherently lends itself to an iterative solution and SQL isn't really suited to that. A Recursive Common Table Expression might be required.
Stefan_Lang 17-Jan-17 1:49am

It should be doable without iteration, but my knowledge of SQL is severely lacking. Basically you need to select all pairs of points and all triplets of points and output the center and radius of the circles they define (for pairs, the center is the mid point), then pipeline the output into another select that for each circle prints the difference of point distance to the circle center (for all points) and circle radius, then select all the circles for which the maximum value of all point distances minus radius is 0, then select the circle with the smallest radius.

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

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

## Solution 6

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

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

```Sheet:
A1= "Points X"
B1= "Points Y"
C1= "Distance"
D1= "Center X"
E1= "Center Y"
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}
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}
Note that 2 points in dataset are on the edge of circle.
v8
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.
Graeme_Grant 8-Jan-17 23:20pm

I have removed my comments after having a closer look at Excel Solver. The "Brute force" approach is an interesting one but it is doing the work for you, a bit like asking someone else to do your job/homework like Solution 4. ;)

## Solution 5

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

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

```class Program
{
static void Main(string[] args)
{
var points = new List<Tuple<double, double>>()
{
new Tuple<double, double>(0.5, 0.75 ),
new Tuple<double, double>(1.25, 0.85),
new Tuple<double, double>(3.86, 2.19),
new Tuple<double, double>(2.11, 4.65),
new Tuple<double, double>(1.17, 2.01),
new Tuple<double, double>(3.19, 1.63),
new Tuple<double, double>(4.87,5.39)
};

var center = new Tuple<double, double>((points.Min(v => v.Item1) + points.Max(v => v.Item1)) / 2, (points.Min(v => v.Item2) + points.Max(v => v.Item2)) / 2);

var radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5));

var IsInCircle = new Func<Tuple<double, double>, bool>((pt) => Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2));

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 --");
}
}```

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

```class Program
{
static void Main(string[] args)
{
var points = new List<(double x, double y)>() { (0.5, 0.75), (1.25, 0.85), (3.86, 2.19), (2.11, 4.65), (1.17, 2.01), (3.19, 1.63), (4.87, 5.39) };

(double x, double y) center = ((points.Min(v => v.x) + points.Max(v => v.x)) / 2, (points.Min(v => v.y) + points.Max(v => v.y)) / 2);
double radius = points.Max(pt => Math.Round(Math.Sqrt(Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2)), 5));

var IsInCircle = new Func<(double x, double y), bool>((pt) => Math.Pow(pt.x - center.x, 2) + Math.Pow(pt.y - center.y, 2) <= Math.Pow(radius, 2));

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 --");
}
}```

** UPDATE #1: Added VB version

```Sub Main()

Dim points = New List(Of Tuple(Of Double, Double)) _
({
New Tuple(Of Double, Double)(0.5, 0.75),
New Tuple(Of Double, Double)(1.25, 0.85),
New Tuple(Of Double, Double)(3.86, 2.19),
New Tuple(Of Double, Double)(2.11, 4.65),
New Tuple(Of Double, Double)(1.17, 2.01),
New Tuple(Of Double, Double)(3.19, 1.63),
New Tuple(Of Double, Double)(4.87, 5.39)
})

Dim center As New Tuple(Of Double, Double)((points.Min(Function(v) v.Item1) + points.Max(Function(v) v.Item1)) / 2, (points.Min(Function(v) v.Item2) + points.Max(Function(v) v.Item2)) / 2)

Dim radius = points.Max(Function(pt) Math.Round(Math.Sqrt(Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2)), 5))

Dim IsInCircle = New Func(Of Tuple(Of Double, Double), Boolean)(Function(pt) Math.Pow(pt.Item1 - center.Item1, 2) + Math.Pow(pt.Item2 - center.Item2, 2) <= Math.Pow(radius, 2))

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 --")

End Sub```

** Update #4: F# version
[note: Thanks to Jon McKee, I took the plunge into F# and this is what resulted from my crash course in learning a second new language in a day. So please forgive me if there is a better way...]
```open System

let points = [(0.5, 0.75);
(1.25, 0.85);
(3.86, 2.19);
(2.11, 4.65);
(1.17, 2.01);
(3.19, 1.63);
(4.87, 5.39)]

let minx,miny,maxx,maxy =
points |> List.fold (fun (mx,my,Mx,My) (ax,ay) ->
min mx ax, min my ay,
max Mx ax, max My ay) (999.0,999.0,-999.0,-999.0)

let center:float*float = (minx + maxx) / 2.0, (miny + maxy) / 2.0

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 =
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 --";
0```

Outputs:
```RADIUS: 3.18695  Center: (2.685,3.07)

(0.5,0.75) is inside the circle
(1.25,0.85) is inside the circle
(3.86,2.19) is inside the circle
(2.11,4.65) is inside the circle
(1.17,2.01) is inside the circle
(3.19,1.63) is inside the circle
(4.87,5.39) is inside the circle

-- Press any key to exit --```

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

```\$points = [System.Tuple]::Create(0.5, 0.75),
[System.Tuple]::Create(1.25, 0.85),
[System.Tuple]::Create(3.86, 2.19),
[System.Tuple]::Create(2.11, 4.65),
[System.Tuple]::Create(1.17, 2.01),
[System.Tuple]::Create(3.19, 1.63),
[System.Tuple]::Create(4.87, 5.39)
\$minX = 9999.0; \$minY = 9999.0

\$points | foreach {\$minX=[math]::Min(\$minX, \$_.item1); \$maxX=[math]::Max(\$maxX, \$_.item1); \$minY=[math]::Min(\$minY, \$_.item2); \$maxY=[math]::Max(\$maxY, \$_.item2)}

\$center = [System.Tuple]::Create((\$minX + \$maxX) / 2,(\$minY + \$maxY) / 2)

\$points | foreach {\$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.
v19
Jon McKee 6-Jan-17 23:54pm

Oooo, do an F# version next! =D (just a jest =P)
Graeme_Grant 7-Jan-17 0:00am

Lmao! Thanks for the suggestion... I did think about it but don't really have the time to wrap my head around F# atm... :)
Jon McKee 7-Jan-17 0:04am

You've got another week, no excuses! Lol =)
Graeme_Grant 7-Jan-17 0:05am

I'm working on a very large project ATM... Maybe I can find some time to learn Typescript... :)
Jon McKee 7-Jan-17 0:11am

Best of luck on the project! I've been meaning to learn Powershell since I've heard it's basically Batch++ so that version is very interesting to me =)
Graeme_Grant 7-Jan-17 0:41am

I was the same until today ... I have found it to be super powerful and can't wait to spend more time with it. :)
Graeme_Grant 7-Jan-17 1:55am

Bit the bullet and did a F# version just for you. Was a bit of a challenge but accepted and done. ;)
Graeme_Grant 7-Jan-17 4:32am

Here is an Excel version too... Screenshot of formulas & output[^]

** Update: I've posted a link to the updated spreadsheet where you can play with the numbers and see the results visually charted in real time. Enjoy! :)
Arthur V. Ratz 8-Jan-17 3:12am

I'm afraid that your solution has the number of disadvantages: the first one is that it allows to find just one circle, and another one is that any points from the dataset should *NOT* reside within the border of a circle, which you'll never achieve by using your algorithm. The "geometric mean" formula that your algorithm relies on doesn't allow to find the desired approximation and thus it's impossible to find an appropriate radius of a circle that encloses all points inside and *NOT* at its border.

I've recently made some improvement to my code, so it always allows to find a circle that surrounds all points in the dataset. The correct value of radius is *NOT* 3.18695, *BUT* r = 3.30, to enclose all points and that's the best approximation. I'm very sorry, but my vote is 3 on both of your solutions 5 and 7. Thanks for reading my comment.
Graeme_Grant 8-Jan-17 3:18am

Yes, this solution doesn't satisfy all datasets but I think that you missed a point of the challenge "The circle may intersect points in the set". So the border is allowed.

Solution 7 is a more accurate version that does not have a margin of error found in this solution.
Arthur V. Ratz 8-Jan-17 3:23am

No, I think that the border is not allowed, because the points that reside on the border don't lie within the area enclosed by a circle. The belonging of such points to this area is in question.
Arthur V. Ratz 8-Jan-17 3:27am

And also, see my plot diagram that illustrates the correct solution of this problem: http://imgur.com/a/Oo0ah
Graeme_Grant 8-Jan-17 3:35am

Arthur V. Ratz 8-Jan-17 3:38am

I'm sorry, you're right since "The circle may intersect points in the set."...
Graeme_Grant 8-Jan-17 3:44am

If you are going to judge my solutions with a rating of 3, then all other solutions that make the same assumption as myself should be rated the same by yourself and not just mine. Thank you.
Graeme_Grant 8-Jan-17 3:58am

Solution 7 correctly gives the smallest circle for all datasets applied to it. Deserves better than a "3". I believe, from my own testing, it is the only solution that currently does. I guess that you can say thatI am a little biased. ;)
Graeme_Grant 8-Jan-17 3:44am

The Challenge states: "determine the centre and radius of the smallest circle" and "The circle may intersect points in the set". The challenge is a singular and not a plural request and intersection is allowed.

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

"The devil is in the details..."
Arthur V. Ratz 8-Jan-17 3:48am

Why do you think that multiple solutions cannot be ???
All solutions produced by my code are very close to one another and can be considered to be a single solution.
Graeme_Grant 8-Jan-17 3:51am

It suggests that your margin of error is very large. As stated above, circles have a fixed radius, so only a single enclosing smallest circle, is valid. IE: you can rotate the circle, but the radius and center remain the same. :)

Different story if we were asked to use ovals....
Arthur V. Ratz 8-Jan-17 4:01am

My margin of error is not very large, since you scarcely could find a circle with a smaller radius rather than the one shown in here: http://imgur.com/a/Oo0ah, having a radius 3.3.

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

About ellipses, we just don't discuss it.
Graeme_Grant 8-Jan-17 4:11am

Yes, but your multi-circle assumption is to not intersect any points which is not a valid assumption based on the conditions set for the challenge.

## Solution 1

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

```<pre>#include <cmath>
#include <ctime>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct tagPoint
{
double x;
double y;
} PT;

typedef struct tagCircle
{
double coord_x;
double coord_y;
} 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[])
{
clock_t time_start = std::clock();
{
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)
{
}
}

}

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.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.
v10
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)
Arthur V. Ratz 6-Jan-17 7:03am

But, what particular points from the dataset: { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } }; you've actually taken for this test. In your comment, you provided only central points of a circle and radius. If you take any point from the dataset it should exactly work. The example of computation I've already posted as the reply to ppolymorphe's comment (see. above).
Arthur V. Ratz 6-Jan-17 7:08am

Here's a quick steps for testing the sets of circle's central points and radiuses from the output that should enclose all of the points in the dataset ( { { 0.5, 0.75 }, { 1.25, 0.85 }, { 3.86, 2.19 }, { 2.11, 4.65 }, { 1.17, 2.01 }, { 3.19, 1.63 } } ):

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

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

And at now, don't you still understand my idea of how to solve this particular problem ??
Patrice T 6-Jan-17 7:30am

Hi Arthur,
Having all points inside of circle is only a part of conditions.
If you have at least 2 circles that surround all points, there is another circle with smaller radius that will surround all points too.
Arthur V. Ratz 6-Jan-17 7:34am

Hi ppolymorphe, Who told you that "If you have at least 2 circles that surround all points, there is another circle with smaller radius that will surround all points too...". - from my position it's simply not correct, though. The smaller circle enclosing all points might or might *NOT* exist.
Patrice T 7-Jan-17 4:14am

That is geometry.
Arthur V. Ratz 6-Jan-17 7:48am

And also, let me tell you what exactly my code does: it's simply aiming to iteratively find those coordinates and those radius values by using which we can draw a circle (not ellipse) surrounding all points in the dataset. This is typically done by using circle equation to test if a certain point belongs to a certain circle region with specific coordinates and radius. If we apply those values of a point coordinates, a circle coordinates and radius to the circle equation which is (x - coord_x)^2 + (y - coord_y)^2 <= R^2 and the condition is true, then we simply consider that point (x;y) is surrounded by the circle with coordinates (coord_x; coord_y) with radius equal to 3.

Isn't it clear ??
Patrice T 7-Jan-17 4:21am

My point was not to say that you have points outside of circle.
My point was to spot that the circle is not the smallest.
In your picture, move a center to {1.73,2.53} and you will see that there is a large margin around the dataset if radius is 3 and that it can be reduced.

By the way, thanks for providing a dataset.
Arthur V. Ratz 7-Jan-17 4:29am

ppolymorphe, thanks for your comment. To obtain the circle with smallest radius, just reduce the radius precision_r to 0.01 and gradually after the code execution you'll get a circle with smaller radius surrounding those points. Thanks.
Patrice T 7-Jan-17 4:46am

As the radius reduce, you will see that the number of possibles circles will reduce until 1 remain.
Arthur V. Ratz 7-Jan-17 4:57am

I'm sorry you actually should increase the precision by reducing the parameter precision_r by assigning it 0.01. This will actually give more results including circles with the actually smallest radius possible.

I'm just working to improve my code so it can produce a larger output dataset when the radius precision is increased to 0.01.
Arthur V. Ratz 7-Jan-17 5:31am

Thanks, ppolymorphe for the clarification. I've re-mastered my code and now it's obvious that the smallest radius for this dataset is 2.2.
Kornfeld Eliyahu Peter 9-Jan-17 4:02am

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

## Solution 2

Here is my Solution in VB :

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

```Module Calculate_Points

Dim myPoints As PointF() = {New PointF(1, 1), New PointF(3, 7), New PointF(5, 2), New PointF(-3, -2), New PointF(5, 5), New PointF(2, 2)}
Dim myPoints2 As PointF() = {New PointF(0, 0), New PointF(10, 0), New PointF(0, 10), New PointF(10, 10), New PointF(5, 5), New PointF(2, 2)}

Function GetSurroundingRadius(xyPoints As PointF()) As Double
Dim xMin As Double = xyPoints(0).X
Dim yMin As Double = xyPoints(0).Y
Dim xMax As Double = xyPoints(0).X
Dim yMax As Double = xyPoints(0).Y

For i As Integer = 1 To xyPoints.Length - 1
xMin = Math.Min(xyPoints(i).X, xMin)
xMax = Math.Max(xyPoints(i).X, xMax)
yMin = Math.Min(xyPoints(i).Y, yMin)
yMax = Math.Max(xyPoints(i).Y, yMax)
Next

Dim myWidth As Double = xMax - xMin
Dim myHeight As Double = yMax - yMin
Dim myCenter As New PointF(myWidth / 2 + xMin, myHeight / 2 + yMin)

Dim myRadius As Double = 0.0

Dim AK As Double = 0.0
Dim GK As Double = 0.0
Dim Hyp As Double = 0.0

For i As Integer = 0 To xyPoints.Length - 1
GK = Math.Abs(myCenter.Y - xyPoints(i).Y)
AK = Math.Abs(myCenter.X - xyPoints(i).X)
Hyp = Math.Sqrt(GK ^ 2 + AK ^ 2)
Next

End Function

Sub Test()
Dim r As Single = GetSurroundingRadius(myPoints2)
Dim a = 1
End Sub

End Module```

I tried to make it simple ... ;-)
v3
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

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?

## Solution 3

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

```#include "stdafx.h"

#include <iostream>
#include <cmath>
#include <unordered_set>

using namespace std;

class point
{
public:
double x, y;
point(std::unordered_set<double,double>::const_iterator &it){}
point(double d1 =0.0, double d2=0.0) : x(d1), y(d2) {};
point(const point& ref) :x(ref.x), y(ref.y) {}
};

bool operator==(const point& lhs, const point& rhs)
{
return (lhs.x == rhs.x && lhs.y == rhs.y);
}

namespace std
{
template <> struct std::hash<point>
{
size_t operator()(point const & x) const noexcept
{
return static_cast<size_t>((15 + std::hash<double>()(x.x) * 15 + std::hash<double>()(x.y)));
}
};
}

double dist(const point &p1, const point &p2) noexcept //computes the distance between two 2d points.
{
return std::sqrt( fabs(p1.x - p2.x) * fabs(p1.x - p2.x) + fabs(p1.y - p2.y) * fabs(p1.y - p2.y)	);
}

int main()
{
unordered_set<point> points{ point(0, 0), point(4, 4) };
double result = 0.0, temp = 0.0;
point centre;

for (auto it = points.begin(); it != points.end(); it++)
{
for (auto it2 = it; it2 != points.end(); it2++)
{
temp = dist(*it, *it2);
if (temp > result)
{
centre.x = fabs((it->x + it2->x) / 2);
centre.y = fabs((it->x + it2->y) / 2);
result = temp;
}
}
}

std::cout << "Radius of minimum bounding circle = " << result / 2 << endl;
std::cout << "Centre of circle = " << centre.x << "," << centre.y << endl;
return 0;
}```
v6
Rob Philpott 6-Jan-17 5:43am

Slightly bothered that I am concerning myself with this problem, but...

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

Cut a square in half diagonally to make a triangle, the farthest points are on the hypotenuse, so centre point would be half way along it. Draw a circle here r=h/2 and all 3 points touch it. Now edge the point of the triangle out a bit. It is outside the circle but doesn't affect that farthest points...
Rajesh R Subramanian 6-Jan-17 5:55am

Hi Rob, thanks for taking the time to comment. You could be 100% right here, but based on what I have understood of your comment, "edging the triangle out a bit" part. If the triangle is edged out, then the points have moved, so it would invalidate the calculation. By "edging" if you mean rotating on the axis of the centre point, then all the points that are already on the circumference would rotate ON the circumference of the circle. I also didn't mention in the original solution, but there could be more than two points on the circumference of the circle. However, I think that wouldn't affect the solution since the distance to that point from the centre will still be the same as what we've calculated.
Rob Philpott 6-Jan-17 6:16am

Ah, it'd be better if computers had pens than keyboards!

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

I think I now know what you're saying. :(

Now I'm having another think. Thanks for bringing this up, Rob. You're awesome!
Rob Philpott 6-Jan-17 6:35am

Yes, saying things are just wrong without offering any alternative solution and without troubling my own brain on how this might be solved makes me think I should move into management. Good luck!
Rajesh R Subramanian 6-Jan-17 6:14am

I took a right angled triangle as a test case, and wanted to verify that it works correctly. The co-ordinates are 0,0 and 4,4. The program output was: Radius of minimum bounding circle = 2.82843
Centre of circle = 2,2

I checked that with Wolfram Alpha and the results seem to be the same: https://www.wolframalpha.com/input/?i=distance+between+(2,2)+to+(0,0)
Patrice T 7-Jan-17 4:53am

I fear point 2 is also wrong. Depending on dataset, it is 2 or 3 points on the edge of circle.
Rajesh R Subramanian 7-Jan-17 19:56pm

Thanks for posting. You're 100% right. I figured that out after a bit of thinking following Rob's post. :-)
Stefan_Lang 17-Jan-17 3:03am

Assumptions 2, 3 and 4 are all incorrect: Consider a point set with 1000 points within the unit circle, and two points at (999.0, 0.0) and (1000.0, 0.0). The latter two points are the farthest away from the mean point, which is somewhere very close or even within the unit circle, but only the last point can be on the optimal circle boundary. Also, assumptions 3 and 4 fail miserably in this example.

## Solution 4

Obvious Solution:

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

Sorry, couldn't resist.
Tachyonx 6-Jan-17 6:26am

Ha ha ... this is a virtual solution thus using delegation,
valid approach, clear and simple ...
Chris Maunder 6-Jan-17 10:30am

You get half a point.
Jon McKee 6-Jan-17 14:13pm

Thank you for making me laugh so hard I got weird looks from people :thumbsup:
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...
Patrice T 8-Jan-17 6:26am

LOL
CPallini 9-Jan-17 6:49am

5. Sorry, couldn't resist.
Graeme_Grant 10-Jan-17 20:18pm

A shame that as this is a "coding challenge" that "no code" & "humor only" does not qualify...

## Solution 12

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

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

```using System;
using System.Collections.Generic;

namespace MinimumBoundingCircle
{
class Program
{
struct PointF
{
public float X;
public float Y;
}
static void Main(string[] args)
{
Console.Out.WriteLine("Enter a comma delimited list of X and Y values:");
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]);
}
var cent = GetCenter(vals.ToArray());
Console.Out.WriteLine("CenterX: " + cent.X);
Console.Out.WriteLine("CenterY: " + cent.Y);
Console.Out.WriteLine("Press enter key to exit...");
}
//Calculates the center point of a collection of points using
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
Press any key to exit...```
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.

## Solution 16

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

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

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

## Solution 9

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

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

So the required program is simply to set up a 2-d matrix whose values are the distances between the points, then scan this to find two points with minimum distance. So easy that the code is not worth writing explicitly.
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.
pwasser 9-Jan-17 18:48pm

The problem is not to find any circle enclosing the data. That is child's play for which your proposal is the evidence. The problem is to find the smallest circle.
Member 12941311 9-Jan-17 19:20pm

Apologies. I realized later that my 'solution' was at best an initial approach, not a solution. I'll give it further thought. I wonder, however, whether an analytic solution is possible, or only a computational solution.
Patrice T 9-Jan-17 20:30pm

Use the Reply button on right of member name to answer a comment.
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

Top Experts
Last 24hrsThis month
 Richard MacCutchan 168 Richard Deeming 120 Afzaal Ahmad Zeeshan 110 KarstenK 75 CPallini 75
 OriginalGriff 2,188 Richard MacCutchan 1,911 CPallini 868 RickZeeland 548 Richard Deeming 510