29
\$\begingroup\$

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:

\$\endgroup\$
  • \$\begingroup\$ Link to sandbox post \$\endgroup\$ – Barranka Jun 23 at 19:08
  • 8
    \$\begingroup\$ “if there are three (non co-linear) points, it's possible to get the equation of a circle that touches them all”—but that may not be the smallest enclosing circle. For the three vertices of an obtuse triangle, the smallest enclosing circle is the one whose diameter is the longest side. \$\endgroup\$ – Anders Kaseorg Jun 23 at 22:17
  • 2
    \$\begingroup\$ @Arnauld Same as you. For test case 2, I get center (-1.73, 0.58) and for test case 3 (5.5, -4). \$\endgroup\$ – Robin Ryder Jun 23 at 22:47
  • \$\begingroup\$ @Arnauld thanks for your comment. I have edited the post accordingly \$\endgroup\$ – Barranka Jun 24 at 1:19
  • \$\begingroup\$ @Arnauld oops, sorry. Indeed. Aldo, correcting with your observations \$\endgroup\$ – Barranka Jun 24 at 13:36
26
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ I was expecting a Mathematica built-in. But I wasn't expecting Mathematica to have "disk objects". \$\endgroup\$ – Robin Ryder Jun 23 at 23:10
  • \$\begingroup\$ 36 bytes to get the output format right: Append@@BoundingRegion[#,"MinDisk"]& \$\endgroup\$ – Roman Jun 24 at 11:23
20
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ maybe writing a Newton-type numerical optimizer is shorter... \$\endgroup\$ – qwr Jun 24 at 15:48
  • \$\begingroup\$ Do you have a proof of correctness? I can see that this is a plausible approach, but more than that seems to require quite a bit of work. \$\endgroup\$ – Peter Taylor Jun 25 at 12:04
  • 3
    \$\begingroup\$ @PeterTaylor The algorithm is mentioned on Wikipedia: a naive algorithm solves the problem in time O(n^4) by testing the circles determined by all pairs and triples of points. But unfortunately, there's no link to a proof. \$\endgroup\$ – Arnauld Jun 25 at 12:46
  • \$\begingroup\$ Will it meet problem of precision making there no solution? \$\endgroup\$ – l4m2 Jun 25 at 15:33
  • 1
    \$\begingroup\$ @Arnauld If you need some strange numbers to reach, I may say that's fine; If it even fail in easy situation that may be a problem \$\endgroup\$ – l4m2 Jun 25 at 15:57
14
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't understand this code, but rather than diameters and circumcircles separately, could you generate all sets of three points with duplicates and filter out the lists of three identical points? \$\endgroup\$ – lirtosiast Jun 25 at 17:22
2
\$\begingroup\$

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⍵}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! Since you are using Python 2, you can save 1 byte by converting the two spaces on the 5th line to a tab. \$\endgroup\$ – Stephen Jun 30 at 3:22
  • \$\begingroup\$ P={x+y*1j for x,y in input()} saves 2 bytes as well. \$\endgroup\$ – Mr. Xcoder Jul 4 at 17:00
1
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ This can be golfed some more. For example, you can shorten if g>c:\n c=g\n d=[e,f] to if g>c:c=g;d=[e,f], saving you a lot of whitespace. I don't think you need to initialise d beforehand, also using two variables and E,F=e,f in line 10 will make your print a lot shorter. I think a solution with max and a list comprehension would be even shorter than two loops, but I might be wrong. Sadly, however, your solution is not correct. For the points (-1,0), (0,1.41), (0.5, 0), (1,0) your solution computes a circle around 0 with radius 1. But the point (1, 1.41) is not in that circle. \$\endgroup\$ – Black Owl Kai Jun 26 at 15:41
  • \$\begingroup\$ Welcome! Thank you for your answer. As pointed in the comment above, your solution is not correct. A hint for brute-force solution: The smallest possible circle touches either two points or three points. You can start calculating the equation for the circle that touches each pair of points and check if there's one that encloses all points. Then calculate the equation for the circle that touches each triplet of points and check if there's one that encloses all points. Once you get all the possible circles, select the one with the smallest radius. \$\endgroup\$ – Barranka Jun 26 at 16:13
  • 1
    \$\begingroup\$ Alright I'm gonna try to make it work, and then I will update the answer. I need to figure out how to check if a point is contained in a circle. \$\endgroup\$ – Ben Morrison Jun 26 at 16:58
  • \$\begingroup\$ Once you have the center and radius of the circle, check if the distance between the center and each point is less than or equal to the radius; if that condition is true for all points, that circle is a candidate \$\endgroup\$ – Barranka Jun 26 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.