Kugelförmiger Überschuss eines Dreiecks

15

Kugelförmiger Überschuss eines Dreiecks

Wie wir alle wissen, beträgt die Winkelsumme eines ebenen Dreiecks 180 Grad.

Bei einem sphärischen Dreieck ist die Winkelsumme jedoch immer größer als 180 Grad. Die Differenz zwischen der Summe der sphärischen Dreieckswinkel und 180 Grad wird als sphärischer Überschuss bezeichnet . Die Aufgabe besteht darin, den sphärischen Überschuss eines Dreiecks mit gegebenen Scheitelpunktkoordinaten zu berechnen.

Etwas Hintergrund

Ein sphärisches Dreieck ist ein Teil der Kugel, der durch drei große Kreise der Kugel definiert wird.

Beide Seiten und Winkel des sphärischen Dreiecks werden als Winkelmaß gemessen, da jede Seite als Schnittpunkt der Kugel mit einem planaren Winkel mit dem Scheitelpunkt in der Mitte der Kugel betrachtet werden kann:

Sphärisches Dreieck erklärt

Jeweils drei verschiedene Großkreise definieren 8 Dreiecke, aber wir berücksichtigen nur die richtigen Dreiecke , d. H. Dreiecke, deren Winkel und Seitenmaße genügen

0 <a, b, c, A, B, C <\ pi

Es ist praktisch, Eckpunkte eines Dreiecks als geografisches Koordinatensystem zu definieren. Um die Länge eines Kugelbogens bei gegebener Länge λ und Breite Φ seiner Enden zu berechnen, können wir die Formel verwenden:

d = 2 r \ arcsin \ left (\ sqrt {\ operatorname {haversin} (\ phi_2 - \ phi_1) + \ cos (\ phi_1) \ cos (\ phi_2) \ operatorname {haversin} (\ lambda_2- \ lambda_1)} \richtig)

, wo

\ operatorname {haversin} (\ theta) = \ sin ^ 2 \ left (\ frac {\ theta} {2} \ right) = \ frac {1- \ cos (\ theta)} {2}

oder genauer gesagt:

d = 2 r \ arcsin \ left (\ sqrt {\ sin ^ 2 \ left (\ frac {\ phi_2 - \ phi_1} {2} \ right) + \ cos (\ phi_1) \ cos (\ phi_2) \ sin ^ 2 \ left (\ frac {\ lambda_2 - \ lambda_1} {2} \ right)} \ right)

(Quelle: https://en.wikipedia.org/wiki/Haversine_formula )

Die zwei Grundformeln, die zum Lösen eines sphärischen Dreiecks verwendet werden können, sind:

  • das Gesetz der Cosinus:

\ cos a = \ cos b \ cos c + \ sin b \ sin c \ cos A, \ cos b = \ cos c \ cos a + \ sin c \ sin a \ cos B, \ cos c = \ cos a \ cos b + \ sin a \ sin b \ cos C

  • das Gesetz der Sinus:

\ frac {\ sin A} {\ sin a} = \ frac {\ sin B} {\ sin b} = \ frac {\ sin C} {\ sin c}

(Quelle: https://en.wikipedia.org/wiki/Spherical_trigonometry#Cosine_rules_and_sine_rules )

Bei drei gegebenen Seiten ist es einfach, die Winkel unter Verwendung der Kosinusregel zu berechnen:

A = \ arccos \ frac {\ cos a - \ cos b \ cos c} {\ sin b \ sin c}, B = \ arccos \ frac {\ cos b - \ cos c \ cos a} {\ sin c \ sin a}, C = \ arccos \ frac {\ cos c - \ cos a \ cos b} {\ sin a \ sin b}

Schließlich wird der kugelförmige Überschuss eines Dreiecks definiert:

E = A + B + C - \ pi

Was ist interessant an der Beziehung zwischen dem sphärischen Überschuss eines Dreiecks und seiner Fläche:

S = E \ cdot R ^ 2

Auf einer Einheitskugel entspricht der Überschuss eines Dreiecks der Fläche dieses Dreiecks!

Die Aufgabe

Schreiben Sie eine Funktion oder ein Programm, das den sphärischen Überschuss eines Dreiecks in Grad berechnet, wenn die Eckpunktkoordinaten des Dreiecks gegeben sind. Die Scheitelpunktkoordinaten werden als geografisches Koordinatensystem angegeben.

Jeder Eckpunkt sollte in Form übergeben werden [latitude in degrees][N|S][longitude in degrees][E|W]. Längengrad und Eoder Wkönnen übersprungen werden, wenn der Breitengrad 90 ist . 90N, 90S, 10N100E, 30S20WSind richtige Vertex Beschreibungen, während 80Noder 55Snicht sind.

Die Breiten- und Längengrade sind in den Testfällen immer ganzzahlig.

Die Antworten mit einem Fehler von weniger als einem Grad werden akzeptiert (wie in den folgenden Beispielen). Das Ergebnis kann daher je nach Bedarf sowohl als reelle als auch als ganze Zahl dargestellt werden.

Beispiele

Eingang

90N0E
0N0E
0N90E

Ausgabe

89.999989

Eingang

90N
0N0E
0N90E

Ausgabe

89.999989

Eingang

0N0E
0N179E
90N0E

Ausgabe

178.998863

Eingang

10N10E
70N20W  
70N40E

Ausgabe

11.969793

In allen Testfällen sind Längen- und Breitengrad ganze Zahlen. Parsen der Vertex - Koordinaten der Teil der Aufgabe ist es , so eine Ecke muss als Einzelsaite / wörtliche weitergegeben wird, ist es nicht erlaubt passieren 80N20Eals vier Parameter / Strings: 80, N, 20, E.

Dies stellt sicher, dass alle Scheitelpunkte unterschiedlich sind und keiner der drei Scheitelpunkte ein antipodales Punktpaar bildet.

Wertung

Das ist , also gewinnt der kürzeste Code.

pawel.boczarski
quelle
1
Die korrekten Ausgaben für die ersten Testfälle sind 90 Grad und 179 Grad. Ich verstehe, dass Sie sagen, dass sie nicht genau stimmen müssen, aber wie viele Dezimalstellen sind erforderlich?
Level River St
@steveverrill Die Aufgabe wurde aktualisiert. Genauigkeit von einem Grad ist genug.
pawel.boczarski
@ pawel.boczarski Sind Breiten- / Längengrade immer ganze Zahlen?
Fehler
@flawr Ja, ich habe die Aufgabe aktualisiert.
pawel.boczarski

Antworten:

4

Matlab, 288 266 Bytes

Hier die kommentierte Version, die erklären soll, was los ist:

                                  %parsing the input
for k=1:3;
    s=input('','s');              %request input
    if sum(s>57)<2;               %if we have only one letter, add arbitrary second coordinate
        s=[s,'0E'];
    end;
    S=1-2*(s(s>57)>80);           %calculate the sign of the coordinates
    s(s>57)=44;                   %replace letters with comma
    L(k,:)=eval(['[',s,']']).*S;  %evaluates string as list and multiply with signs
end;
i=[2,3,1];
                                  %calculate the angular distance between each pair of points
a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*pi/180;
                                  %evaluate the spherical excess
f=@(a,b,c)sum(acos((cos(a)-cos(b).*cos(c))./(sin(b).*sin(c))))-pi;
disp(f(a,a(i),a([3,1,2]))*180/pi)

Vollgolf (Zeilenumbrüche können entfernt werden):

for k=1:3;s=input('','s');if sum(s>57)<2;s=[s,'0E'];end;
s(s>57)=44;L(k,:)=eval([91,s,93]).*(1-2*(s(s<48)>80));end;
i=[2,3,1];p=pi/180;a=arrayfun(@distance,L(:,1),L(:,2),L(i,1),L(i,2))*p;
b=a(i);disp((sum(acos((cos(a([3,1,2]))-cos(b).*cos(a))./(sin(b).*sin(a))))-pi)/p)
fehlerhaft
quelle
3

Ruby, Rev 3 264 255 Bytes

Wesentliche Änderungen:

Neue Konstante r= 180 / PI definiert und in der gesamten Funktion verwendet. eMusste auf + PI initialisiert werden, so zählt Überschuss jetzt abwärts und wird vor der Rückkehr negiert.

t[]eliminiert: Ruby ermöglicht die t[]direkte Zuordnung der Daten, denen zugewiesen wurdeu,v,w.

Einzelschleife ifür die Ausführung von zwei ?:ternären Bedienern, die zwischen Aufgaben wechseln.

Viele andere kleine Änderungen.

include Math
->s{r=180/e=PI
x=y=z=n=[]
9.times{|i|i<6?(u,v,w=eval(?[+s[i%3].gsub(/[NE]/,"/r,").gsub(/[SW]/,"/-r,")+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u))+(y*=cos(v)*w=cos(u))+x*=w*sin(v)):e-=acos((n[i-7]-(c=n[i-6])*d=n[i-8])/sqrt((1-c*c)*(1-d*d)))}
-e*r}

Ruby, Rev 1 283 277 Bytes

Benötigt ein Array von 3 Zeichenfolgen.

include Math 
->s{x=y=z=n=[]
6.times{|i|t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
i%2<1&&x=y=z=1
n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))}
e=-PI
3.times{|i|e+=acos((n[i-1]-n[i]*d=n[i-2])/sqrt((1-n[i]**2)*(1-d**2)))}
e/PI*180}

Überblick

Die Längen der Dreieckseiten auf der Einheitskugel entsprechen den Winkeln zwischen den Vektoren, die die beiden Punkte beschreiben. Aber diesen Winkel brauchen wir nicht zu kennen. Es genügt, den Kosinus des Winkels zu kennen, der mit dem Skalarprodukt leicht aus kartesischen Koordinaten ermittelt werden kann.

Erläuterung

Die Eingabezeichenfolgen werden in eine Zeichenfolgendarstellung eines Arrays konvertiert, das dann wie folgt ausgewertet und gespeichert twird. Die endgültige Null wird nicht benötigt, wenn zwei Koordinaten angegeben sind. Wenn nur der Breitengrad 90 angegeben ist, wird die Null als Längengrad interpretiert.

Example:  70N20W --> [70*PI/180,20*-1*PI/180,0]

Die Dot-Produkte haben die Form a.b=ax*bx+ay*by+az*bz. Da die Vektoren alle eine Einheitslänge haben, ist das Punktprodukt gleich dem Kosinus des Winkels zwischen den Vektoren.

Um sie zu berechnen, wird eine Schleife sechsmal durchlaufen, wobei zweimal die Eingabedaten durchlaufen werden. Bei den geraden Iterationen 0,2,4 werden die Variablen x,y,zauf 1 gesetzt, um eine neue Berechnung zu starten. Bei jeder Iteration werden diese Variablen mit den x-, y- und z-Komponenten jedes Vektors multipliziert, wobei die in gespeicherten Längen- und Breitengraddaten verwendet werden t[0],t[1](denen aus Golfgründen auch zugewiesen wird u,v). Die Summe der Variablen wird in das Array geschrieben n(die Abfallwerte bei geraden Iterationen werden durch die korrekten Werte bei ungeraden Iterationen überschrieben), sodass am Ende ndie 3 Punktprodukte enthalten sind [a.b, c.a, b.c].

Für die Cosinusregel benötigen wir den Cosinus der drei eingeschlossenen Winkel zwischen Eckpunkten, aber wir benötigen auch den Sinus. Diese werden erhalten als sqrt(1-cosine**2). Wenn die Sinusse multipliziert werden, kann der Ausdruck neu angeordnet werden, sodass nur ein Aufruf von sqrterforderlich ist. Die Tatsache, dass wir nicht wissen, ob der Sinus positiv oder negativ war, spielt keine Rolle, da die Haversinusformel sowieso immer den positiven Sinus ergibt. Die wichtige physikalische Größe ist der Abstand zwischen den Punkten, der absolut und daher immer positiv ist.

Für jede Iteration i=0..2berechnen wir den Wert für das gegenüberliegende Array-Element i-1mit den anderen Elementen iund i-2. Negative Array-Indizes wie dieses sind in Ruby zulässig. Sie werden nur an den Anfang des Arrays umgebrochen.

Ungolfed im Testprogramm

Erfordert drei Koordinatensätze auf derselben Linie mit Leerzeichen dazwischen.

include Math
g=->s{
  n=[]         #array for dot products
  x=y=z=1      #it's required to use these variables once before the loop, for some bizarre reason
  6.times{|i|
    t=eval(?[+s[i%3].gsub(/[NE]/,k="*PI/180,").gsub(/[SW]/,"*-1"+k)+"0]")
    i%2<1&&x=y=z=1
    n[i/2]=(z*=sin(u=t[0]))+(y*=cos(u)*cos(v=t[1]))+(x*=cos(u)*sin(v))
  }

  e=-PI        #set e to -PI and begin accumulating angles
  3.times{|i|
    e+=acos((n[i-1]-n[i]*n[i-2])/sqrt((1-n[i]**2)*(1-n[i-2]**2)))
  }

e/PI*180}      #return value

puts g[gets.split]
Level River St
quelle