Volume lambung cembung 3D dari titik kecil mengatur semua pada lambung

11

Saya punya pertanyaan yang mirip dengan yang diajukan sebelumnya kecuali dalam 3D, dan saya hanya perlu volume, bukan bentuk lambung yang sebenarnya.

Lebih tepatnya, saya diberi satu set kecil poin (katakanlah, 10-15) dalam 3D, yang semuanya diketahui terletak pada cembung lambung set point (sehingga mereka semua "penting" dan mendefinisikan lambung). Saya hanya ingin menghitung volume lambung, saya tidak peduli tentang menghitung polyhedron yang sebenarnya. Apakah ada algoritma yang efisien untuk melakukan ini?

Victor Liu
sumber
Anda tahu bahwa titik adalah simpul dari polyhedron. Apakah Anda tahu wajah-wajah (poligon di lambung kapal)? Jika demikian, Anda dapat menghitung volume dengan mudah (sebagai jumlah volume "kerucut").
hardmath
1
Cara malas akan melakukan triangulasi terlebih dahulu, kemudian menjumlahkan volume tetrahedra (sangat mudah untuk dihitung).
Shuhao Cao
@hardmath: Tidak. Saya tahu bahwa jika saya tahu bentuk fasetnya, itu akan mudah.
Victor Liu
@ Shuhao Cao: Apakah ada algoritma triangulasi sederhana untuk kasus khusus ini? Algoritma tetrahedralization 3D umumnya cukup rumit, dan saya berharap perlu menyelesaikan masalah ini ribuan atau jutaan kali.
Victor Liu

Jawaban:

5

Saya akan terkejut jika Anda bisa mengalahkan saran Shuhao Cao: hitung lambung dan kemudian volumenya begitu Anda memiliki triangulasi lambung. Anda dapat menghitung lambung dengan algoritma tambahan , atau algoritma pembungkusan hadiah. Jika Anda benar-benar menginginkan kode mudah, Anda cukup menulis lingkaran n 4 di atas semua segitiga yang mungkin untuk melihat apakah ada di lambung. Untuk n = 15 , ini masih cukup cepat, dan Anda dapat dengan mudah menerapkan pintasan. Setelah Anda memiliki semua wajah segitiga, lalu pilih satu simpul v dan buat tetrahedron dengan setiap segitiga T dan v . Volumenya adalah 4 ×HAI(n2)n4n=15vTv penentu dalam koordinat titik.4×4

Joseph O'Rourke
sumber
2

Sebuah tes kecil dalam MATLAB, untuk jumlah simpul , setiap komponen adalah angka acak seragam dalam [ 0 , 1 ] :N=100[0,1]

N = 100;
p=rand(N,3);
tic;
T = delaunayTri(p(:,1),p(:,2),p(:,3));
t = T.Triangulation;
e1 = p(t(:,2),:)-p(t(:,1),:);
e2 = p(t(:,3),:)-p(t(:,1),:);
e3 = p(t(:,4),:)-p(t(:,1),:);
V = abs(dot(cross(e1,e2,2),e3,2))/6;
Vol = sum(V);
time_elapse = toc;

Hasil:

time_elapse =
              0.014807
Vol =
      0.67880219135839

Saya akan mengatakan itu cukup cepat, jika Anda ingin menjalankannya kali, itu hanya membutuhkan waktu kurang dari 3 jam. Seperti apa ini:106

Conhull

4×4N=105

time_elapse =
              3.244278
Vol =
     0.998068316875714

7×1051[0,1]3

Shuhao Cao
sumber
BTW tes dilakukan pada 2007 Core 2 T61p saya yang lama.
Shuhao Cao
2

Dari FAQ Komputasi Polihedral Komei Fukuda :

Rd

Diketahui bahwa menghitung volume V-polytope (atau H-polytope) adalah # P-hard, lihat [DF88] dan [Kha93]. Ada algoritma acak yang efisien secara teoritis untuk memperkirakan volume benda cembung [LS93] tetapi tampaknya tidak ada implementasi yang tersedia. Ada studi perbandingan [BEF00] dari berbagai algoritma perhitungan volume untuk poltop cembung. Ini menunjukkan bahwa tidak ada algoritma tunggal yang bekerja dengan baik untuk berbagai jenis polytopes.

[DF88] ME Dyer dan AM Frieze. Kompleksitas menghitung volume polihedron. SIAM J. Comput. , 17: 967-974, 1988.

[Kha93] LG Khachiyan. Kompleksitas perhitungan volume polytope. Dalam J. Pach, editor, Tren Baru dalam Geometri Diskrit dan Komputasi , halaman 91-101. Springer Verlag, Berlin, 1993.

[LS93] L. Lovasz dan M. Simonovits. Acak berjalan dalam tubuh cembung dan algoritma volume yang ditingkatkan. Struktur & algoritma acak , 4: 359-412, 1993.

[BEF00] B. Bueler, A. Enge, dan K. Fukuda. Perhitungan volume yang tepat untuk polytopes cembung: Studi praktis. Dalam G. Kalai dan GM Ziegler, editor, Polytopes - Combinatorics and Computation , DMV-Seminar 29, halaman 131-154. Birkhauser, 2000.

Hal ini tampaknya mengubur masalah 3D di antara kesulitan dimensi yang lebih tinggi, meskipun judul makalah Dyer dan Frieze. Dari Abstrak: "Kami menunjukkan bahwa menghitung volume polyhedron yang diberikan baik sebagai daftar segi atau sebagai daftar simpul sama sulitnya dengan menghitung permanen dari sebuah matriks."

PPNvvPPPP={xR3:SEBUAHxb}

P

hardmath
sumber