El problema:

Dado un conjunto de puntos no vacío en el plano cartesiano, encuentre el círculo más pequeño que los encierra a todos ( enlace de Wikipedia ).

Este problema es trivial si el número de puntos es tres o menos (si hay un punto, el círculo tiene un radio de cero; si hay dos puntos, el segmento de línea que une los puntos es el diámetro del círculo; si hay tres puntos (no colineales), es posible obtener la ecuación de un círculo que los toca a todos si forman un triángulo no obtuso, o un círculo que toca solo dos puntos y encierra el tercero si el triángulo es obtuso). Entonces, por el bien de este desafío, el número de puntos debería ser mayor que tres.

El reto:

Entrada: una lista de 4 o más puntos no colineales. Los puntos deben tener coordenadas X e Y; Las coordenadas pueden ser flotadores. Para facilitar el desafío, no hay dos puntos que compartan la misma coordenada X.
Por ejemplo:[(0,0), (2,1), (5,3), (-1,-1)]
Salida: una tupla de valores, de (h,k,r)modo que $(x-h)^2 + (y-k)^2 = r^2$ es la ecuación del círculo más pequeño que encierra todos los puntos.

Reglas:

Puede elegir el método de entrada que se adapte a su programa.
La salida debe ser impresa STDOUTo devuelta por una función.
Se prefieren los idiomas "normales", de uso general, pero cualquier esolang es aceptable.
Puede suponer que los puntos no son colineales.
Este es el código de golf, por lo que gana el programa más pequeño en bytes. El ganador será seleccionado una semana después de que se publique el desafío.
- Incluya el idioma que utilizó y la longitud en bytes como encabezado en la primera línea de su respuesta: # Language: n bytes

Casos de prueba:

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

¡Feliz golf!

Desafío relacionado:

Área de un casco convexo 2D

code-golf geometry Barranka
fuente

Enlace al post sandbox

Barranka

8

"Si hay tres puntos (no co-lineales), es posible obtener la ecuación de un círculo que los toca a todos", pero puede que no sea el círculo más pequeño. Para los tres vértices de un triángulo obtuso, el círculo cerrado más pequeño es aquel cuyo diámetro es el lado más largo.

Anders Kaseorg

2

@Arnauld Igual que tú. Para el caso de prueba 2, obtengo el centro (-1.73, 0.58) y para el caso de prueba 3 (5.5, -4).

Robin Ryder

@Arnauld gracias por tu comentario. He editado la publicación en consecuencia

Barranka

@Arnauld, perdón. En efecto. Aldo, corrigiendo con sus observaciones

Barranka

26

Wolfram Language (Mathematica) , 28 27 bytes

#~BoundingRegion~"MinDisk"&

Pruébalo en línea!

Los empotrados son útiles aquí. La salida es un objeto de disco con el centro y el radio. Como otros, he encontrado que los casos de la segunda y tercera prueba son diferentes a la pregunta.

¡Gracias a @lirtosiast por guardar un byte!

Si se requiere una lista como salida, esto puede hacerse en 35 bytes (a costa de 8 bytes adicionales) . Gracias a @Roman por señalar esto.

Nick Kennedy
fuente

3

Esperaba un Mathematica incorporado. Pero no esperaba que Mathematica tuviera "objetos de disco".

Robin Ryder

36 bytes para obtener el formato de salida correcto:Append@@BoundingRegion[#,"MinDisk"]&

Roman

20

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

Devuelve una matriz [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

Pruébalo en línea!

o ver una versión formateada

¿Cómo?

Método

Para cada par de puntos $(A,B)$ , generamos el círculo $(X,Y,r)$ cuyo diámetro es $AB$ .

X = \frac{{UNA}_{X} + {si}_{X}}{2}, Y = \frac{{UNA}_{y} + {si}_{y}}{2}, r = \sqrt{{(\frac{{UNA}_{X} - {si}_{X}}{2})}^{2} + {(\frac{{UNA}_{y} - {si}_{y}}{2})}^{2}}

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

Para cada triple de puntos distintos $(A,B,C)$ , que generan el círculo $(X,Y,r)$ que circunscribe el triángulo $ABC$ .

re = {UNA}_{X} ({si}_{y} - {do}_{y}) + {si}_{X} ({do}_{y} - {UNA}_{y}) + {do}_{X} ({UNA}_{y} - {si}_{y})

$d=A_x(B_y-C_y)+B_x(C_y-A_y)+C_x(A_y-B_y)$

X = \frac{({UNA}_{X}^{2} + {UNA}_{y}^{2}) ({si}_{y} - {do}_{y}) + ({si}_{X}^{2} + {si}_{y}^{2}) ({do}_{y} - {UNA}_{y}) + ({do}_{X}^{2} + {do}_{y}^{2}) ({UNA}_{y} - {si}_{y})}{2 re}

$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{({UNA}_{X}^{2} + {UNA}_{y}^{2}) ({do}_{X} - {si}_{X}) + ({si}_{X}^{2} + {si}_{y}^{2}) ({UNA}_{X} - {do}_{X}) + ({do}_{X}^{2} + {do}_{y}^{2}) ({si}_{X} - {UNA}_{X})}{2 re}

$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 - {UNA}_{X})^{2} + (Y - {UNA}_{y})^{2}}

$r=\sqrt{(X-A_x)^2+(Y-A_y)^2}$

$(x,y)$

\sqrt{(X - X)^{2} + (y - Y)^{2}} \leq r

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

Y finalmente devolvemos el círculo válido más pequeño.

Implementación

$(X,Y)$ $d\neq0$ $q={C_x}^2+{C_y}^2$

X = \frac{({UNA}_{X}^{2} + {UNA}_{y}^{2} - q) ({si}_{y} - {do}_{y}) + ({si}_{X}^{2} + {si}_{y}^{2} - q) ({do}_{y} - {UNA}_{y})}{2 re}

$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{({UNA}_{X}^{2} + {UNA}_{y}^{2} - q) ({do}_{X} - {si}_{X}) + ({si}_{X}^{2} + {si}_{y}^{2} - q) ({UNA}_{X} - {do}_{X})}{2 re}

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

$F$ $(j,k)$

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

$F$ $s$ $(X,Y)$ $d=0$

Arnauld
fuente

quizás escribir un optimizador numérico tipo Newton es más corto ...

qwr

¿Tienes una prueba de corrección? Puedo ver que este es un enfoque plausible, pero más que eso parece requerir bastante trabajo.

Peter Taylor

3

@PeterTaylor El algoritmo se menciona en Wikipedia: un algoritmo ingenuo resuelve el problema en el tiempo O (n ^ 4) probando los círculos determinados por todos los pares y triples de puntos . Pero desafortunadamente, no hay un enlace a una prueba.

Arnauld

¿Resolverá el problema de precisión haciendo que no haya solución?

l4m2

1

@Arnauld Si necesita algunos números extraños para alcanzar, puedo decir que está bien; Si incluso falla en una situación fácil, eso puede ser un problema

l4m2

14

R , 59 bytes

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

Pruébalo en línea!

Toma la entrada como un vector de coordenadas complejas. Modes la distancia (módulo) en el plano complejo y nlmes una función de optimización: encuentra la posición del centro (salida como estimate) que minimiza la distancia máxima a los puntos de entrada y proporciona la distancia correspondiente (salida comominimum ), es decir, el radio . Preciso de 3-6 dígitos; el pie de página TIO redondea la salida a 2 dígitos.

nlmtoma un vector numérico como entrada: la y%*%c(1,1i)empresa lo convierte en complejo.

Robin Ryder
fuente

9

Jalea , 100 98 bytes

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

Pruébalo en línea!

En contraste con mi respuesta del lenguaje Wolfram , Jelly necesita bastante código para lograr esto (¡a menos que me falte algo!). Este programa completo toma la lista de puntos como argumento y devuelve el centro y el radio del círculo cerrado más pequeño. Genera círculos para todos los conjuntos de tres puntos y diámetros para todos los conjuntos de dos puntos, verifica los que incluyen todos los puntos y luego selecciona el que tiene el radio más pequeño.

El código para el bit make_circumcircle se inspiró en el código de este sitio , a su vez inspirado en Wikipedia.

Nick Kennedy
fuente

1

No entiendo este código, pero en lugar de los diámetros y los círculos por separado, ¿podría generar todos los conjuntos de tres puntos con duplicados y filtrar las listas de tres puntos idénticos?

lirtosiast el

2

APL (NARS), 348 caracteres, 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⍵}

Esta es una 'implementación' de fórmulas en la solución Arnauld ... Resultados y comentarios:

  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: encuentra la combinación de alfa ojets en el conjunto omega

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

((X, Y), r) a partir de ahora representan una circunferencia de radio r y centro en (XY).

c: encuentra si el punto en ⍺ está dentro de la circunferencia ((XY) r) en ⍵ (resultado <= 0) ot es externo (resultado> 0) En el caso de entrada de circunferencia en ⍵ es ⍬ como entrada, devolvería 1 (fuera de circunferencia) cada entrada posible en ⍺.

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

p: si ⍵ es una matriz de ((XY) r); para cada uno de los ((XY) r) en ⍵ escribe 1 si todos los puntos en la matriz ⍺ son internos a ((XY) r) de lo contrario escribe 0 NB Aquí hay algo que no funciona porque tuve que redondear a epsilon = 1e¯ 13) en otras palabras, en casos límite de puntos en el plano (y probablemente construido a propósito) no está 100% asegurado por la solución

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

s2: desde 2 puntos en ⍵, devuelve la circunferencia en el formato ((XY) r) que tiene diámetro en esos 2 puntos

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

s3: desde 3 puntos devuelve la circunferencia en el formato ((XY) r) que pasa por esos tres puntos Si hay problemas (por ejemplo, los puntos están alineados), fallaría y devolvería ⍬.

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

tenga en cuenta que -. × encuentre el determinante de una matriz nxn y

  ⎕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: a partir de n puntos en ⍵, encuentra las circunferencias de tipo de las encontradas por s2 o las de tipo s3 que contienen todos los n puntos.

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

s1: del conjunto encontrado en el s anterior calcula aquellos que tienen radio mínimo y devuelve el primero que tiene radio mínimo. Los tres números como matrices (la primera y la segunda coordenadas son las coordenadas del centro, mientras que la tercera es el radio de la circunferencia encontrada).

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

RosLuP
fuente

2

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]

Pruébalo en línea!

Esto utiliza el algoritmo de fuerza bruta O (n ^ 4), iterando a través de cada par y triángulo de puntos, calculando el centro y manteniendo el centro que necesita el radio más pequeño para encerrar todos los puntos. Calcula el circuncentro de 3 puntos al encontrar la intersección de dos bisectrices perpendiculares (o, si dos puntos son iguales, usa el punto medio con el tercero).

Vash3r
fuente

Bienvenido a PPCG! Como está utilizando Python 2, puede guardar 1 byte al convertir los dos espacios en la quinta línea en una pestaña.

Stephen

P={x+y*1j for x,y in input()}ahorra 2 bytes también.

Sr. Xcoder

1

Pitón 212 190 bytes

Esta solución es incorrecta y tengo que trabajar ahora, así que no tengo tiempo para solucionarlo.

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

Pruébalo en línea!

¡Descubrí qué dos puntos están más lejos y luego generé una ecuación para un círculo basada en esos puntos!

Sé que esto no es lo más corto en python, ¡pero es lo mejor que puedo hacer! Además, este es mi primer intento de hacer uno de estos, ¡así que comprendan!

Ben Morrison
fuente

2

Esto se puede jugar un poco más. Por ejemplo, puede acortar if g>c:\n c=g\n d=[e,f]a if g>c:c=g;d=[e,f], ahorrándole mucho espacio en blanco. No creo que necesite inicializar d de antemano, también usando dos variables y E,F=e,fen la línea 10 lo hará printmucho más corto. Creo que una solución maxy una comprensión de la lista sería incluso más corta que dos bucles, pero podría estar equivocado. Lamentablemente, sin embargo, su solución no es correcta. Para los puntos (-1,0), (0,1.41), (0.5, 0), (1,0) su solución calcula un círculo alrededor de 0 con radio 1. Pero el punto (1, 1.41) no está en ese circulo.

Black Owl Kai

¡Bienvenido! Gracias por su respuesta. Como se señaló en el comentario anterior, su solución no es correcta. Una pista para la solución de fuerza bruta: el círculo más pequeño posible toca dos puntos o tres puntos. Puede comenzar a calcular la ecuación para el círculo que toca cada par de puntos y verificar si hay uno que incluya todos los puntos. Luego calcule la ecuación para el círculo que toca cada triplete de puntos y verifique si hay uno que incluya todos los puntos. Una vez que obtenga todos los círculos posibles, seleccione el que tenga el radio más pequeño.

Barranka

1

Bien, intentaré que funcione, y luego actualizaré la respuesta. Necesito descubrir cómo verificar si un punto está contenido en un círculo.

Ben Morrison

Una vez que tenga el centro y el radio del círculo, verifique si la distancia entre el centro y cada punto es menor o igual que el radio; si esa condición es verdadera para todos los puntos, ese círculo es un candidato

Barranka

¡Golf el círculo más pequeño!

El problema:

El reto:

Reglas:

Casos de prueba:

Desafío relacionado:

Respuestas:

Wolfram Language (Mathematica) , 28 27 bytes

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

¿Cómo?

Método

Implementación

R , 59 bytes

Jalea , 100 98 bytes

APL (NARS), 348 caracteres, 696 bytes

Python 2 (PyPy) , 244 242 bytes

Pitón 212 190 bytes