Berechnen Sie den Fermatpunkt eines Dreiecks

12

Dies ähnelt in gewisser Weise den Mittelpunkten eines Dreiecks , hat jedoch einen anderen Punkt. Der Fermat-Punkt ist der Punkt P im Dreieck ABC, so dass der Wert von AP + BP + CP minimiert wird. Es gibt zwei Fälle:

Wenn ein Winkel größer als 120 Grad ist, ist dieser Scheitelpunkt der Fermatpunkt. Zeichnen Sie andernfalls gleichseitige Dreiecke an jeder Seite von ABC. Verbinden Sie den äußersten Scheitelpunkt jedes gleichseitigen Dreiecks mit dem gegenüberliegenden Scheitelpunkt des Dreiecks ABC. Wenn Sie dies für jedes der drei gleichseitigen Dreiecke tun, erhalten Sie einen gemeinsamen Schnittpunkt für alle drei Linien, den Fermat-Punkt.

Es sollte innerhalb von 5 Sekunden auf einem vernünftigen Computer ausgeführt werden.

Eingabe : Ein Satz von 3 Punkten, nicht unbedingt ganze Zahlen. Dies kann als verschachteltes Array, als Zeichenfolge, als Liste von Tupeln usw. verwendet werden (je nachdem, was für Ihre Sprache geeignet ist).

Ausgabe : Die Koordinaten des Fermat-Punkts, jedoch behandelt Ihre Sprache Punkte am besten. Fließkomma-Ungenauigkeiten werden nicht mitgezählt.

Testfälle :

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

Das ist Codegolf, also gewinnt der kürzeste Code!

soktinpk
quelle
1
Ist es in Ordnung, alle Punkte in Gleitkomma-Schritten zu testen und den Punkt auszuwählen, der die Gesamtentfernung minimiert?
xnor
1
@xnor Wenn du es innerhalb von 5 Sekunden schaffst.
Soktinpk
Bis zu wie vielen signifikanten Zahlen muss die Ausgabe genau sein? Ist es auch in Ordnung, wenn -0.0anstelle einiger 0.0s ausgegeben wird ?
R. Kap
@R. Kap Ich würde sagen, über 5 oder 6 signifikante Figuren. Es gibt nicht so viel, dass Rundungsfehler ein Problem sein sollten. Die zweite Frage scheint in Ordnung zu sein.
Soktinpk

Antworten:

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)

Derselbe Code mit einigen Erklärungen

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

Tests:

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

Ausgabe:

[1.2113248654051871,1.7886751345948126]
[-1.0,-1.0]
[0.0,-0.42264973081037427]
[0.0,0.0]
[0.0,0.0]
Damien
quelle
Wie zählen Sie Bytes? £ und ¤ sind jeweils 2 Byte in UTF-8, und ich kenne keinen Haskell-Compiler, der ISO-8859-1 akzeptiert. (Sie haben jedoch viele freie 1-Byte-ASCII-Operatoren, sodass dies leicht zu beheben ist.)
Anders Kaseorg
Ich zähle es mit meinem Editor, der tatsächlich Zeichen zählt. Ich wusste nicht, dass dies 2 Bytes sind, aber wie Sie sagten, könnte ich es durch andere 1-Byte-Operatoren ersetzen. Dieser Code kompiliert mit GHC 7.8.3
Damien
GHC kompiliert Ihren Code, wenn er als UTF-8 mit £und ¤als 2-Byte-Operatoren codiert ist, jedoch nicht, wenn er als ISO-8859-1 mit £und ¤als 1-Byte-Operatoren codiert ist . Die zur Verfügung stehenden 1 - Byte - Operatoren in UTF-8 !, #, %, &, ?. Sie sollten die 2-Byte-Operatoren ersetzen oder Ihre Byteanzahl anpassen.
Anders Kaseorg
2

Python, 475 448 440 Bytes

Jede weitere Hilfe zum Golfen ist willkommen.

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

Ungolfed:

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

Eingang:

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

Ausgabe:

[1.2113248652983113, 1.7886751347016887]
[-1, -1]
[0.0, -0.42264973086764884]
[0, 0]
[0, 0]
abybaddi009
quelle
2
from math import*ist ein ziemlich häufiges Golfspiel. Dadurch können Sie es auch verwenden, pianstatt es hart zu codieren (gleiche Länge für 2*pi/3). Sie können auch sehr viele Leerzeichen fallen wie: 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]

Unglaublich lange im Vergleich zu anderen Antworten, aber hey, zumindest funktioniert es! Ich könnte mit dem Ergebnis nicht zufriedener sein, da dies eine der schwierigsten Herausforderungen sein muss, die ich je gemacht habe. Ich bin einfach so froh, dass es tatsächlich funktioniert! : D Nun zu den technischen Anmerkungen:

  • Diese Funktion nimmt jedes geordnete Paar als Liste oder Tupel auf. Zum Beispiel H((1,1),(2,2),(1,2))wird funktionieren, aber auch H([1,1],[2,2],[1,2]).
  • Gibt die Koordinaten der Punkte in einer Liste von Ganzzahlen oder Gleitkommazahlen aus, je nachdem, ob ein Winkel größer oder gleich 120 ° vorhanden ist.
  • Dies kann Ausgabe -0.0anstelle der 0.0für einige Eingaben. Zum Beispiel kann der Ausgang für die Eingabe [-1, -1], [1, -1], [0, 1]ist [-0.0, -0.4226497308103744]. Ich hoffe, das ist in Ordnung, aber wenn nicht, werde ich es ändern, obwohl es mich ein paar Bytes mehr kosten wird. Dies ist in Ordnung, wie vom OP bestätigt .
  • Sollte mindestens 13auf 14signifikante Zahlen genau sein .

Ich werde versuchen, dies im Laufe der Zeit noch weiter zu verbessern. Eine Erklärung, möglicherweise sehr lang, kommt bald.

Probieren Sie es online! (Ideone)

R. Kap
quelle
1

Mathematica, 39 Bytes

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

Konstruiert eine Gleichung basierend auf den Abständen zwischen den Eckpunkten und einem Punkt {x,y}. Verwenden Sie dann die NArgMinFunktion, um ein globales Minimum für diese Gleichung zu finden, bei dem es sich per Definition um den Fermat-Punkt handelt.

Beispiel

Meilen
quelle
1
39 Bytes, wenn die nächste kürzeste Antwort 285 ist ...
Bálint