Oblicz punkt Fermata w trójkącie

13

Jest to nieco podobne do centrów trójkąta , ale z innym punktem. Fermat Punkt jest punktem P w trójkącie ABC takie, że wartość AP + BP + CP jest zminimalizowane. Istnieją dwa przypadki:

Jeśli kąt jest większy niż 120 stopni, ten wierzchołek jest punktem końcowym. W przeciwnym razie narysuj trójkąty równoboczne po każdej stronie ABC. Połącz najdalszy wierzchołek każdego trójkąta równobocznego z przeciwległym wierzchołkiem trójkąta ABC. Wykonanie tego dla każdego z trzech trójkątów równobocznych powoduje powstanie jednego wspólnego punktu przecięcia dla wszystkich trzech linii, którym jest Punkt Fermata.

Powinien działać w ciągu 5 sekund na rozsądnej maszynie.

Dane wejściowe : zestaw 3 punktów, niekoniecznie liczb całkowitych. Może to być traktowane jako zagnieżdżona tablica, łańcuch, lista krotek itp. (Cokolwiek pasuje do twojego języka).

Wyjście : ponownie współrzędne punktu Fermata, jednak twój język najlepiej obsługuje punkty. Niedokładności zmiennoprzecinkowe nie będą liczone przeciwko tobie.

Przypadki testowe :

[[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]

To jest golf golfowy, więc wygrywa najkrótszy kod!

soktinpk
źródło
1
Czy można wypróbować wszystkie punkty w przyrostach precyzji zmiennoprzecinkowej i wybrać ten, który minimalizuje całkowitą odległość?
xnor
1
@xnor Jeśli możesz to zrobić w ciągu 5 sekund.
soktinpk
Do ilu znaczących liczb wynik musi być dokładny? Czy jest w porządku, jeśli -0.0dane wyjściowe są zastępowane przez niektóre 0.0s?
R. Kap
@R. Kap Powiedziałbym około 5 lub 6 znaczących liczb. Nie ma tak wiele, że błędy zaokrąglania powinny stanowić problem. Co do drugiego pytania, wydaje się to w porządku.
soktinpk

Odpowiedzi:

3

Haskell, 346 291 285 bajtów

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)

Ten sam kod z kilkoma objaśnieniami

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

Testy:

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

Wynik:

[1.2113248654051871,1.7886751345948126]
[-1.0,-1.0]
[0.0,-0.42264973081037427]
[0.0,0.0]
[0.0,0.0]
Damien
źródło
Jak liczyć bajty? £ i ¤ mają po 2 bajty w UTF-8 i nie znam kompilatora Haskell, który akceptuje ISO-8859-1. (Masz jednak wiele bezpłatnych 1-bajtowych operatorów ASCII, więc łatwo to naprawić.)
Anders Kaseorg
Liczę to za pomocą mojego edytora, który faktycznie liczy znaki. Nie wiedziałem, że były to 2 bajty, ale tak jak powiedziałeś, mogłem je zastąpić innymi 1 bajtowymi operatorami. Ten kod kompiluje się z GHC 7.8.3
Damien
GHC kompiluje kod gdy zakodowany jako UTF-8 £i ¤jako 2 operatorów bajtowych, ale nie wtedy, gdy zakodowany jako ISO-8859-1 z £i ¤jako 1 bajt operatorów. Dostępne operatory 1 bajt w UTF-8 są !, #, %, &, ?. Należy wymienić 2 bajty operatorów lub dostosować liczbę bajtów.
Anders Kaseorg,
2

Pyton, 475 448 440 bajtów

Każda pomoc w golfie jest doceniana.

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

Nie golfowany:

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

Wejście:

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

Wynik:

[1.2113248652983113, 1.7886751347016887]
[-1, -1]
[0.0, -0.42264973086764884]
[0, 0]
[0, 0]
abybaddi009
źródło
2
from math import*jest dość powszechnym golfem. Pozwoli to również na użycie pizamiast kodowania na stałe (dla tej samej długości 2*pi/3). Można również spaść dużo białych znaków takich jak: d=lambda x,y:(....
FryAmTheEggman
2

Python 3.5, 1019 1016 998 982 969 953 bajtów:

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]

Niewiarygodnie długi w porównaniu do innych odpowiedzi, ale hej, przynajmniej działa! Nie mógłbym być bardziej zadowolony z wyniku, który uzyskałem, ponieważ musi to być jedno z najtrudniejszych wyzwań, jakie kiedykolwiek podjąłem. Jestem tak szczęśliwy, że to naprawdę działa! : D Teraz, do bardziej technicznych uwag:

  • Ta funkcja przyjmuje każdą uporządkowaną parę jako listę lub krotkę. Na przykład H((1,1),(2,2),(1,2))będzie działać, ale tak będzie H([1,1],[2,2],[1,2]).
  • Podaje współrzędne punktów na liście liczb całkowitych lub zmiennoprzecinkowych, w zależności od tego, czy istnieje jeden kąt większy lub równy 120º.
  • Może to generować -0.0zamiast 0.0niektórych danych wejściowych. Na przykład dane wyjściowe dla danych wejściowych [-1, -1], [1, -1], [0, 1]to [-0.0, -0.4226497308103744]. Mam nadzieję, że jest to w porządku, chociaż jeśli nie, zmienię to, choć będzie mnie to kosztowało jeszcze kilka bajtów. Jest to w porządku, co potwierdza OP .
  • Powinny być dokładne co najmniej 13do 14znaczących liczb.

Z czasem spróbuję zagrać w golfa. Wyjaśnienie, być może bardzo długie, już wkrótce.

Wypróbuj online! (Ideone)

R. Kap
źródło
1

Mathematica, 39 bajtów

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

Konstruuje równanie na podstawie odległości między wierzchołkami i punktem {x,y}. Następnie używa NArgMinfunkcji do znalezienia globalnego minimum dla tego równania, które z definicji będzie punktem Fermata.

Przykład

mile
źródło
1
39 bajtów, gdy następna najkrótsza odpowiedź to 285 ...
Bálint