Kelebihan bola berbentuk segitiga

Seperti yang kita semua tahu, jumlah sudut dari setiap segitiga planar sama dengan 180 derajat.

Namun, untuk segitiga berbentuk bola, jumlah sudut selalu lebih besar dari 180 derajat. Perbedaan antara jumlah sudut segitiga bola dan 180 derajat disebut kelebihan bola . Tugasnya adalah untuk menghitung kelebihan bola dari segitiga dengan koordinat titik yang diberikan.

Beberapa latar belakang

Segitiga bola adalah bagian dari bola yang didefinisikan oleh tiga lingkaran besar bola.

Kedua sisi dan sudut segitiga bola diukur dalam istilah ukuran sudut, karena setiap sisi dapat dianggap sebagai persimpangan bola dan beberapa sudut planar dengan simpul di tengah bola:

Masing-masing tiga lingkaran besar yang berbeda menentukan 8 segitiga, tetapi kami hanya mempertimbangkan segitiga yang tepat , yaitu. segitiga yang ukuran sudut dan sampingnya memuaskan

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

Lebih mudah untuk mendefinisikan simpul segitiga dalam hal sistem koordinat geografis. Untuk menghitung panjang busur bola diberikan garis bujur λ dan garis lintang Φ dari ujungnya kita dapat menggunakan rumus:

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

dimana

$\ operatorname {haversin} (\ theta) = \ sin ^ 2 \ kiri (\ frac {\ theta} {2} \ kanan) = \ frac {1- \ cos (\ theta)} {2}$

atau lebih tepatnya:

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

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

Dua formula dasar yang dapat digunakan untuk memecahkan segitiga bola adalah:

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

hukum sinus:

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

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

Diberikan tiga sisi, mudah untuk menghitung sudut menggunakan aturan cosinus:

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

Akhirnya, kelebihan bola dari segitiga didefinisikan:

$E = A + B + C - \ pi$

Apa yang menarik tentang hubungan antara kelebihan bola segitiga dan luasnya:

$S = E \ cdot R ^ 2$

Jadi pada unit sphere, kelebihan sebuah segitiga sama dengan luas segitiga itu!

Tugas

Tulis fungsi atau program yang akan menghitung kelebihan bola dari segitiga dalam derajat yang diberikan koordinat segitiga simpul. Koordinat titik disediakan dalam hal sistem koordinat geografis.

Setiap titik harus dilewatkan dalam bentuk [latitude in degrees][N|S][longitude in degrees][E|W]. Bujur dan Eatau Wdapat dilewati ketika lintang adalah 90 yaitu. 90N, 90S, 10N100E, 30S20WAdalah deskripsi vertex yang tepat, sementara 80Natau 55Stidak.

Garis lintang dan bujur selalu bilangan bulat dalam kasus uji.

Jawaban dengan kesalahan kurang dari satu derajat akan diterima (seperti dalam contoh di bawah). Hasilnya dapat ditampilkan sebagai nyata atau bilangan bulat, hingga kenyamanan Anda.

Contohnya

Memasukkan

90N0E
0N0E
0N90E

Keluaran

89.999989

Memasukkan

90N
0N0E
0N90E

Keluaran

89.999989

Memasukkan

0N0E
0N179E
90N0E

Keluaran

178.998863

Memasukkan

10N10E
70N20W  
70N40E

Keluaran

11.969793

Dalam semua kasus uji, bujur dan lintang adalah bilangan bulat. Parsing koordinat titik adalah bagian dari tugas, sehingga simpul harus dilalui sebagai satu string / literal, itu tidak diperbolehkan untuk melewati 80N20Eempat parameter / string: 80, N, 20, E.

Ini dijamin bahwa semua simpul berbeda dan tak satu pun dari tiga simpul membuat pasangan antipodal.

Mencetak gol

Ini kode-golf , jadi kode terpendek menang.

code-golf geometry trigonometry pawel.boczarski
sumber

Output yang benar untuk beberapa kasus uji pertama adalah 90 derajat dan 179 derajat. Saya mengerti Anda mengatakan bahwa mereka tidak harus tepat, tetapi berapa banyak tempat desimal akurasi yang diperlukan?

Level River St

@steveverrill Memperbarui tugas. Akurasi satu derajat sudah cukup.

pawel.boczarski

@ pawel.boczarski Apakah lintang / bujur selalu bilangan bulat?

flawr

@ flawr Ya, saya memperbarui tugas.

pawel.boczarski

Jawaban:

Matlab, 288 266 bytes

Di sini versi komentar yang harus menjelaskan apa yang sedang terjadi:

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

Sepenuhnya golf (linebreak dapat dihapus):

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)

cacat
sumber

Ruby, Rev 3 264 255 byte

Perubahan besar:

Konstanta baru r= 180 / PI didefinisikan dan digunakan di seluruh fungsi. eharus diinisialisasi ke + PI, jadi kelebihan sekarang dihitung ke bawah dan dinegasikan sebelum kembali.

t[]dihilangkan: Ruby memungkinkan data yang ditugaskan untuk t[]ditugaskan langsung keu,v,w.

Satu iloop untuk melakukan pekerjaan dua, ?:operator ternary beralih di antara tugas.

Banyak perubahan kecil lainnya.

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

Membutuhkan array 3 string.

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}

Gambaran

Panjang sisi segitiga pada satuan bola sama dengan sudut antara vektor yang menggambarkan dua titik. Tapi kita tidak perlu tahu sudut itu. Cukuplah untuk mengetahui kosinus sudut, yang mudah diperoleh dari koordinat kartesius menggunakan Produk Dot.

Penjelasan

String input dikonversi menjadi representasi string dari array, yang kemudian dievaluasi dan disimpan t, seperti di bawah ini. Nol akhir tidak diperlukan jika dua koordinat diberikan. Jika hanya lintang 90 yang diberikan, nol diartikan sebagai garis bujur.

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

Produk Dot berbentuk a.b=ax*bx+ay*by+az*bz. Karena semua vektor panjang unit, produk titik sama dengan cosinus sudut antara vektor.

Untuk menghitungnya, sebuah loop diulang 6 kali melewati dua kali input data. Pada iterasi genap 0,2,4 variabel x,y,zditetapkan ke 1 untuk memulai perhitungan baru. Pada setiap iterasi, variabel-variabel ini dikalikan dengan komponen x, y dan z dari masing-masing vektor, menggunakan data bujur dan lintang yang disimpan di t[0],t[1]dalamnya (yang karena alasan golf juga ditugaskan u,v). Jumlah variabel ditulis ke array n(nilai-nilai sampah pada iterasi bahkan ditimpa oleh nilai-nilai yang benar pada iterasi aneh) sehingga pada akhirnya nberisi produk 3 titik[a.b, c.a, b.c] .

Untuk aturan cosinus, kita membutuhkan cosinus dari tiga sudut termasuk di antara simpul, tetapi kita juga membutuhkan sinus. Ini diperoleh sebagai sqrt(1-cosine**2). Ketika sinus dikalikan bersama, ekspresi dapat diatur ulang sehingga hanya satu panggilan ke sqrtdiperlukan. Fakta bahwa kita tidak tahu apakah sinus itu positif atau negatif tidak masalah, karena rumus haversine selalu memberikan sinus positif pula. Kuantitas fisik yang penting adalah jarak antara titik-titik, yang mutlak dan karenanya selalu positif.

Untuk setiap iterasi i=0..2, kami menghitung nilai untuk elemen array berlawanan sudut i-1menggunakan elemen lain idan i-2. Subskrip array negatif seperti ini legal di Ruby, mereka hanya membungkus ke awal array.

Tidak digabungkan dalam program uji

Membutuhkan tiga set koordinat pada baris yang sama, dengan spasi di antaranya.

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
sumber