Calcular el punto de Fermat de un triángulo

13

Esto es algo similar a Los centros de un triángulo , pero con un punto diferente. El punto de Fermat es el punto P en el triángulo ABC, de modo que el valor de AP + BP + CP se minimiza. Hay dos casos:

Si hay un ángulo mayor de 120 grados, ese vértice es el punto de fermat. De lo contrario, dibuje triángulos equiláteros en cada uno de los lados de ABC. Conecte el vértice lejano de cada triángulo equilátero al vértice opuesto del triángulo ABC. Hacer esto para cada uno de los tres triángulos equiláteros da como resultado un único punto común de intersección para las tres líneas, que es el punto de Fermat.

Debe ejecutarse dentro de los 5 segundos en una máquina razonable.

Entrada : Un conjunto de 3 puntos, no necesariamente enteros. Esto se puede tomar como una matriz anidada, una cadena, una lista de tuplas, etc. (lo que se adapte a su idioma).

Salida : las coordenadas del punto Fermat, de nuevo, sin embargo, su idioma maneja mejor los puntos. Las imprecisiones de coma flotante no se contarán en su contra.

Casos de prueba :

[[1, 1], [2, 2], [1, 2]] --> [1.2113248654051871, 1.788675134594813]
[[-1, -1], [-2, -1], [0, 0]] --> [-1, -1]
[[-1, -1], [1, -1], [0, 1]] --> [0, -0.42264973081037427]
[[0, 0], [0.5, 0.8660254037844386], [-5, 0]] --> [0, 0]
[[0, 0], [0, -5], [-0.8660254037844386, 0.5]] --> [0, 0]

Este es el código de golf, ¡el código más corto gana!

soktinpk
fuente
1
¿Está bien probar todos los puntos en incrementos de precisión de punto flotante y seleccionar el que minimiza la distancia total?
xnor
1
@xnor Si puedes hacerlo en 5 segundos.
soktinpk
¿Hasta cuántas cifras significativas debe ser precisa la salida? Además, ¿está bien si -0.0se emite en lugar de algunos 0.0s?
R. Kap
@R. Kap yo diría que unas 5 o 6 cifras significativas. No hay tanto que los errores de redondeo sean un problema. En cuanto a la segunda pregunta, eso parece estar bien.
soktinpk

Respuestas:

3

Haskell, 346 291 285 bytes

infixl 5£
z=zipWith
(?)=z(-)
t[a,b]=[-b,a]
a¤b=sum$z(*)a b
a%b=t a¤b
r a b c=[c%b/a%b,c%a/a%b]
x£y=2*x¤y<= -sqrt(x¤x*y¤y)
f[a,b,c]|a?b£c?b=b|a?c£b?c=c|b?a£c?a=a|[n,m,p,o]<-c?k a b c++a?k b c a=r[m,o][n,p][c%[n,m],a%[p,o]]
k a b c=map(/2)$z(+)a b?map(signum((b?a)%(c?a))*sqrt 3*)(t$b?a)

El mismo código con algunas explicaciones.

infixl 5£
z=zipWith

-- operator ? : difference of two vectors
(?)=z(-)            

-- function t : rotate a vector by +90 degrees
t[a,b]=[-b,a]       

-- operator ¤ : scalar product of two vectors ( a¤b = a0 * b0 + a1 * b1 )
a¤b=sum$z(*)a b     

-- operator % : "cross product" of two vectors ( a%b = a0 * b1 - a1 * b0 )
--      this returns actually the z coordinate of the 3d cross vector
--      other coordinates are nul since a and b are in the xy plan
a%b=t a¤b

-- function r : solves the system of two linear equations with two variables x0,x1 :
--      a0*x0 - b0*x1 = c0
--      a1*x0 - b1*x1 = c1
r a b c=[c%b/a%b,c%a/a%b]

-- operator £ : returns true if the angle between two vectors is >= 120 degrees
--      x¤y = ||x|| * ||y|| * cos(xyAngle)
--      so xyAngle>=120° is equivalent to : x¤y / (||x|| * ||y||) <= -0.5
x£y=2*x¤y<= -sqrt(x¤x*y¤y)

-- function k : takes 3 points A B C of a triangle and constructs the point C' 
--              of the equilateral triangle ABC' which is opposite to C:
--              C' = (A+B)/2 - ((+/-) sqrt(3)/2 * t(AB))
--
--      the sign +/- is given by the sign of the cross vector of AB an AC ((b?a)%(c?a))
--      which is >0 if the angle between AB and AC is positive
--      and <0 otherwise.
k a b c=map(/2)$z(+)a b?map(signum((b?a)%(c?a))*sqrt 3*)(t$b?a)

-- function f : returns the fermat point of a triangle
f[a,b,c]
    |a?b£c?b=b  -- return B if angle ABC >= 120°
    |a?c£b?c=c  -- return C if angle BCA >= 120°
    |b?a£c?a=a  -- return A if angle CAB >= 120°
    |[n,m,p,o]<-c?k a b c++a?k b c a= -- calculate the two segments C'C and A'A
        r[m,o][n,p][c%[n,m],a%[p,o]]  -- return their intersection

Pruebas:

main = do 
    print $ f [[1, 1], [2, 2], [1, 2]]
    print $ f [[-1, -1], [-2, -1], [0, 0]]
    print $ f [[-1, -1], [1, -1], [0, 1]]
    print $ f [[0, 0], [0.5, 0.8660254037844386], [-5, 0]]
    print $ f [[0, 0], [0, -5], [-0.8660254037844386, 0.5]]

Salida:

[1.2113248654051871,1.7886751345948126]
[-1.0,-1.0]
[0.0,-0.42264973081037427]
[0.0,0.0]
[0.0,0.0]
Damien
fuente
¿Cómo estás contando bytes? £ y ¤ son 2 bytes cada uno en UTF-8, y no conozco un compilador Haskell que acepte ISO-8859-1. (Sin embargo, tiene muchos operadores ASCII de 1 byte gratuitos, por lo que esto es fácil de solucionar.)
Anders Kaseorg
Lo estoy contando con mi editor, que en realidad cuenta los personajes. No sabía que eran 2 bytes, pero de todos modos, como dijiste, podría reemplazarlo por otros operadores de 1 byte. Este código se compila con GHC 7.8.3
Damien
GHC compila su código cuando se codifica como UTF-8 con £y ¤como operadores de 2 bytes, pero no cuando se codifica como ISO-8859-1 con £y ¤como operadores de 1 byte. Los operadores disponibles 1 byte en UTF-8 son !, #, %, &, ?. Debe reemplazar los operadores de 2 bytes o ajustar su recuento de bytes.
Anders Kaseorg
2

Pitón, 475 448 440 bytes

Cualquier ayuda para el golf más se aprecia.

from math import *
d=lambda x,y:((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5
s=lambda A,B,C:(d(B,C), d(C,A), d(A,B))
j=lambda a,b,c:acos((b*b+c*c-a*a)/(2*b*c))
t=lambda a,b,c:1/cos(j(a,b,c)-pi/6)
b=lambda A,B,C,p,q,r:[(p*A[i]+q*B[i]+r*C[i])/(p+q+r) for i in [0,1]] 
f=lambda A,B,C:A if j(*s(A,B,C)) >= 2*pi/3 else B if j(*s(B,C,A)) >= 2*pi/3 else C if j(*s(C,A,B)) >= 2*pi/3 else b(A,B,C,d(B,C)*t(*s(A,B,C)),d(C,A)*t(*s(B,C,A)),d(A,B)*t(*s(C,A,B)))

Sin golf:

from math import *
#distance between two points
d = lambda x,y: ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5

#given the points, returns the sides 
s = lambda A,B,C : (d(B,C), d(C,A), d(A,B))

#given the sides, returns the angle
j = lambda a,b,c : acos((b*b+c*c-a*a)/(2*b*c))

#given the sides, returns secant of that angle
t = lambda a,b,c: 1/cos(j(a,b,c)-pi/6)

#given the sides and the Trilinear co-ordinates, returns the Cartesian co-ordinates
b = lambda A,B,C,p,q,r: [(p*A[i]+q*B[i]+r*C[i])/(p+q+r) for i in [0,1]] 

#this one checks if any of the angle is >= 2π/3 returns that point else computes the point
f = lambda A,B,C: A if j(*s(A,B,C)) >= 2*pi/3 else B if j(*s(B,C,A)) >= 2*pi/3 else C if j(*s(C,A,B)) >= 2*pi/3 else b(A,B,C,d(B,C)*t(*s(A,B,C)),d(C,A)*t(*s(B,C,A)),d(A,B)*t(*s(C,A,B)))

Entrada:

print('{}'.format(f([1, 1], [2, 2], [1, 2])))
print('{}'.format(f([-1, -1], [-2, -1], [0, 0])))
print('{}'.format(f([-1, -1], [1, -1], [0, 1])))
print('{}'.format(f([0, 0], [0.5, 0.8660254037844386], [-5, 0])))
print('{}'.format(f([0, 0], [0, -5], [-0.8660254037844386, 0.5])))

Salida:

[1.2113248652983113, 1.7886751347016887]
[-1, -1]
[0.0, -0.42264973086764884]
[0, 0]
[0, 0]
abybaddi009
fuente
2
from math import*Es un golf bastante común. Esto también le permitirá usarlo en pilugar de codificarlo (la misma longitud 2*pi/3). También puede dejar una gran cantidad de espacio en blanco como: d=lambda x,y:(....
FryAmTheEggman
2

Python 3.5, 1019 1016 998 982 969 953 bytes:

from math import*
def H(z,a,b):c=complex;T=lambda A,B:abs(c(*A)-c(*B));d=T(z,a);e=T(z,b);f=T(a,b);g=[d,e,f];h=max(g);g.remove(h);i=acos((sum(i*i for i in g)-(h*h))/(2*g[0]*g[-1]));_=[[z,a],[z,b],[a,b]];j,s,t=cos,sin,atan;N=[[b,a]for a,b in zip([b,a,z],[max(i,key=i.get)if i!=''else''for i in[{(g[0]+(h*j(t(l))),g[1]+(h*s(t(l)))):T(k,(g[0]+(h*j(t(l))),g[1]+(h*s(t(l))))),(g[0]-(h*j(t(l))),g[1]-(h*s(t(l)))):T(k,(g[0]-(h*j(t(l))),g[1]-(h*s(t(l)))))}if l else{(g[0]+h,g[1]):T(k,(g[0]+h,g[1])),(g[0]-h,g[1]):T(k,(g[0]-h,g[1]))}if l==0else''for g,h,l,k in zip([((a[0]+b[0])/2,(a[1]+b[1])/2)for a,b in _],[(3**0.5)*(i/2)for i in[d,e,f]],[-1/p if p else''if p==0else 0for p in[((a[1]-b[1])/(a[0]-b[0]))if a[0]-b[0]else''for a,b in _]],[b,a,z])]])if b!=''];I=N[0][0][1];J=N[0][0][0];K=N[1][0][1];G=N[1][0][0];A=(N[0][1][1]-I)/(N[0][1][0]-J);B=I-(A*J);C=(K-N[1][1][1])/(G-N[1][1][0]);D=K-(C*G);X=(D-B)/(A-C);Y=(A*X)+B;return[[X,Y],[[a,b][h==d],z][h==f]][i>2.0943]

Increíblemente largo en comparación con otras respuestas, pero bueno, ¡al menos funciona! No podría estar más feliz con el resultado que obtuve, ya que este debe ser uno de los desafíos más difíciles que he hecho. ¡Estoy tan feliz de que realmente funcione! : D Ahora, en las notas más técnicas:

  • Esta función toma cada par ordenado como una lista o una tupla. Por ejemplo, H((1,1),(2,2),(1,2))funcionará, pero también lo hará H([1,1],[2,2],[1,2]).
  • Emite las coordenadas de los puntos en una lista de enteros o puntos flotantes dependiendo de si existe un ángulo mayor o igual a 120º.
  • Esto puede generar -0.0en lugar de 0.0algunas entradas. Por ejemplo, la salida para la entrada [-1, -1], [1, -1], [0, 1]es [-0.0, -0.4226497308103744]. Espero que esto esté bien, aunque si no lo está, lo cambiaré, aunque me costará unos pocos bytes más. Esto está bien, según lo confirmado por OP .
  • Debe ser exacto hasta al menos 13a 14cifras significativas.

Intentaré jugar más golf con el tiempo. Una explicación, posiblemente muy larga, próximamente.

¡Pruébelo en línea! (Ideona)

R. Kap
fuente
1

Mathematica, 39 bytes

Sum[Norm[p-{x,y}],{p,#}]~NArgMin~{x,y}&

Construye una ecuación basada en las distancias entre los vértices y un punto {x,y}. Luego usa la NArgMinfunción para encontrar un mínimo global para esa ecuación, que será el Punto de Fermat por definición.

Ejemplo

millas
fuente
1
39 bytes, cuando la siguiente respuesta más corta es 285 ...
Bálint