Golf the smallest circle!

Question

The problem:

Given a non-empty set of points in the Cartesian plane, find the smallest circle that encloses them all (Wikipedia link).

This problem is trivial if the number of points is three or less (if there's one point, the circle has a radius of zero; if there are two points, the line segment that joins the points is the diameter of the circle; if there are three (non-colinear) points, it's possible to get the equation of a circle that touches them all if they form a non-obtuse triangle, or a circle that touches only two points and encloses the third if the triangle is obtuse). So, for the sake of this challenge, the number of points should be greater than three.

The challenge:

• Input: A list of 4 or more non-colinear points. The points should have X and Y coordinates; coordinates can be floats. To ease the challenge, no two points should share the same X coordinate.
  For example: [(0,0), (2,1), (5,3), (-1,-1)]
• Output: A tuple of values, (h,k,r), such that \$(x-h)^2 + (y-k)^2 = r^2\$ is the equation of the smallest circle that encloses all points.

Rules:

• You can choose whatever input method suits your program.
• Output should be printed to STDOUT or returned by a function.
• "Normal", general-purpose, languages are preferred, but any esolang is acceptable.
• You can assume that the points are not colinear.
• This is code-golf, so the smallest program in bytes wins. The winner will be selected one week after the challenge is posted.
  • Please include the language you used and the length in bytes as header in the first line of your answer: # Language: n bytes

Test cases:

• 1:
  • Input: [(-8,0), (3,1), (-6.2,-8), (3,9.5)]
  • Output: [-1.6, 0.75, 9.89]
• 2:
  • Input: [(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
  • Output: [-1.73, 0.58, 11.58]
• 3:
  • Input: [(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
  • Output: [5.5, -4, 7.5]
• 4:
  • Input: [(6,6), (-6,7), (-7,-6), (6,-8)]
  • Output: [0, -0.5, 9.60]

Happy golfing!!!

---

Related challenge:

• Area of a 2D convex hull

Answer 1

Wolfram Language (Mathematica), 28 27 bytes

#~BoundingRegion~"MinDisk"&

Try it online!

Built-ins are handy here. Output is a disk object with the centre and radius. Like others, I’ve found the 2nd and 3rd test cases to be different to the question.

Thanks to @lirtosiast for saving a byte!

If a list is required as output, this can be done in 35 bytes (at the cost of an additional 8 bytes). Thanks to @Roman for pointing this out.

Answer 2

JavaScript (ES6),  298 ... 243  242 bytes

Returns an array [x, y, r].

p=>p.map(m=([c,C])=>p.map(([b,B])=>p.map(([a,A])=>p.some(([x,y])=>H(x-X,y-Y)>r,F=s=>Y=(d?((a*a+A*A-q)*j+(b*b+B*B-q)*k)/d:s)/2,d=c*(A-B)+a*(j=B-C)+b*(k=C-A),r=H(a-F(a+b),A-F(A+B,X=Y,j=c-b,k=a-c)))|r>m?0:o=[X,Y,m=r]),q=c*c+C*C),H=Math.hypot)&&o

Try it online!

or see a formatted version

How?

Method

For each pair of points \$(A,B)\$, we generate the circle \$(X,Y,r)\$ whose diameter is \$AB\$.

$$X=\frac{A_x+B_x}{2},\;Y=\frac{A_y+B_y}{2},\;r=\sqrt{\left(\frac{A_x-B_x}{2}\right)^2+\left(\frac{A_y-B_y}{2}\right)^2}$$

For each triple of distinct points \$(A,B,C)\$, we generate the circle \$(X,Y,r)\$ which circumscribes the triangle \$ABC\$.

$$d=A_x(B_y-C_y)+B_x(C_y-A_y)+C_x(A_y-B_y)$$ $$X=\frac{({A_x}^2+{A_y}^2)(B_y-C_y)+({B_x}^2+{B_y}^2)(C_y-A_y)+({C_x}^2+{C_y}^2)(A_y-B_y)}{2d}$$ $$Y=\frac{({A_x}^2+{A_y}^2)(C_x-B_x)+({B_x}^2+{B_y}^2)(A_x-C_x)+({C_x}^2+{C_y}^2)(B_x-A_x)}{2d}$$ $$r=\sqrt{(X-A_x)^2+(Y-A_y)^2}$$

For each generated circle, we test whether each point \$(x,y)\$ is enclosed within it:

$$\sqrt{(x-X)^2+(y-Y)^2}\le r$$

And we eventually return the smallest valid circle.

Implementation

In the JS code, the formula to compute \$(X,Y)\$ for the triangle's circumscribed circle is slightly simplified. Assuming \$d\neq0\$, we define \$q={C_x}^2+{C_y}^2\$, leading to:

$$X=\frac{({A_x}^2+{A_y}^2-q)(B_y-C_y)+({B_x}^2+{B_y}^2-q)(C_y-A_y)}{2d}$$ $$Y=\frac{({A_x}^2+{A_y}^2-q)(C_x-B_x)+({B_x}^2+{B_y}^2-q)(A_x-C_x)}{2d}$$

This way, the helper function \$F\$ requires only two parameters \$(j,k)\$ to compute each coordinate:

• \$(B_y-C_y,\;C_y-A_y)\$ for \$X\$
• \$(C_x-B_x,\;A_x-C_x)\$ for \$Y\$

The third parameter used in \$F\$ (i.e. its actual argument \$s\$) is used to compute \$(X,Y)\$ when \$d=0\$, meaning that the triangle is degenerate and we have to try to use the diameter instead.

Answer 3

R, 59 bytes

function(x)nlm(function(y)max(Mod(x-y%*%c(1,1i))),0:1)[1:2]

Try it online!

Takes input as a vector of complex coordinates. Mod is the distance (modulus) in the complex plane and nlm is an optimization function: it finds the position of the center (output as estimate) which minimizes the maximum distance to the input points, and gives the corresponding distance (output as minimum), i.e. the radius. Accurate to 3-6 digits; the TIO footer rounds the output to 2 digits.

nlm takes a numeric vector as input: the y%*%c(1,1i) business converts it to a complex.

Answer 4

Jelly, 100 98 bytes

_²§½
1ịṭƊZIṚṙ€1N1¦,@ṭ@²§$µḢZ���×Ø1œị$SḤ÷@P§
ZṀ+ṂHƲ€_@Ç+ḷʋ⁸,_²§½ʋḢ¥¥
œc3Ç€;ŒcZÆm,Hñ/$Ʋ€$ñ_ƭƒⱮṀ¥Ðḟ⁸ṚÞḢ

Try it online!

In contrast to my Wolfram language answer, Jelly needs quite a lot of code to achieve this (unless I’m missing something!). This full program takes the list of points as its argument and returns the centre and radius of the smallest enclosing circle. It generates circumcircles for all sets of three points, and diameters for all sets of two points, checks which include all of the points and then picks the one with the smallest radius.

Code for the make_circumcircle bit was inspired by code at this site, in turn inspired by Wikipedia.

Answer 5

Python 2 (PyPy), 244 242 bytes

P={complex(*p)for p in input()}
Z=9e999,
for p in P:
 for q in{p}^P:
	for r in{p}^P:R,S=1j*(p-q),q-r;C=S.imag and S.real/S.imag-1jor 1;c=(p+q-(S and(C*(p-r)).real/(C*R).real*R))/2;Z=min(Z,(max(abs(c-t)for t in P),c.imag,c.real))
print Z[::-1]

Try it online!

This uses the brute-force O(n^4) algorithm, iterating through each pair and triangle of points, calculating the centre, and keeping the centre that needs the smallest radius to enclose all points. It calculates the circumcentre of 3 points via finding the intersection of two perpendicular bisectors (or, if two points are equal it uses the midpoint with the third).

Answer 6

APL(NARS), 348 chars, 696 bytes

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

This is one 'implementation' of formulas in Arnauld solution...Results and comments:

  s1 (¯8 0)(3 1)(¯6.2 ¯8)(3 9.5)
¯1.6 0.75  9.885469134 
  s1 (7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
¯1.732305109 0.5829680042  11.57602798 
  s1 (0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
5.5 ¯4  7.5 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)
0 ¯0.5  9.604686356 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
2 ¯1.5  11.67261753 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)(7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
1.006578947 ¯1.623355263  12.29023186 
  s1 (1 1)(2 2)(3 3)(4 4)
2.5 2.5  2.121320344 
  ⎕fmt s3 (1 1)(2 2)(3 3)(4 4)
┌0─┐
│ 0│
└~─┘

f: finds the combination of alpha ojets in the omega set

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

((X,Y), r) from now represent one circonference of radius r and center in (X Y).

c: finds if the point in ⍺ is inside the circumference ((X Y) r) in ⍵ (result <=0) ot it is external (result >0) In the case of circumference input in ⍵ it is ⍬ as input, it would return 1 (out of circumference) each possible input in ⍺.

c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}

p: if ⍵ is an array of ((X Y) r); for each of the ((X Y) r) in ⍵ writes 1 if all points in the array ⍺ are internal to ((X Y) r) otherwise writes 0 NB Here's something that do not goes because I had to round to epsilon= 1e¯13. in other words in limit cases of points in the plane (and probably built on purpose) it is not 100% solution insured

p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}

s2: from 2-point in ⍵, it returns the circumference in the format ((X Y) r) that has diameter in those 2 points

s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}

s3: from 3 points it return the circumference in the format ((X Y) r) passing through those three points If there are problems (for example points are aligned), it would fail and return ⍬.

s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}

note that -.× find the determinant of a matrix nxn and

  ⎕fmt ⊃{⍵,1}¨(¯8 0)(3 1)(¯6.2 ¯8)
┌3─────────┐     
3 ¯8    0 1│     |ax  ay 1|
│  3    1 1│   d=|bx  by 1|=ax(by-cy)-bx(ay-cy)+cx(ay-by)=ax(by-cy)+bx(cy-ay)+cx(ay-by)
│ ¯6.2 ¯8 1│     |cx  cy 1|
└~─────────┘

s: from n points in ⍵, it finds the type circumferences of those found by s2 or those of type s3 that contain all n points.

s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}

s1: from the set found from the s above calculates those that have minimum radius and returns the first one that has minimal radius. The three numbers as arrays (the first and second coordinates are the coordinates of the center, while the third is the radius of the circumference found).

s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

Answer 7

Python 212 190 bytes

This solution is incorrect, and I have to work now so I do not have time to fix it.

a=eval(input())
b=lambda a,b: ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
c=0
d=1
for e in a:
    for f in a:
        g=b(e,f)
        if g>c:
            c=g
            d=[e,f]
print(((d[0][0]+d[1][0])/2,(d[0][1]+d[1][1])/2,c/2))

Try it online!

I figured out which two points are furthest and then I generated an equation for a circle based off those points!

I know this isn't the shortest in python, but it's the best I could do! Also this is my first attempt at doing one of these, so please be understanding!