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?
algorithms
reference-request
computational-geometry
Victor Liu
sumber
sumber
Jawaban:
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 ×O ( n2) n4 n = 15 v T v penentu dalam koordinat titik.4 × 4
sumber
Sebuah tes kecil dalam MATLAB, untuk jumlah simpul , setiap komponen adalah angka acak seragam dalam [ 0 , 1 ] :N= 100 [ 0 , 1 ]
Hasil:
Saya akan mengatakan itu cukup cepat, jika Anda ingin menjalankannya kali, itu hanya membutuhkan waktu kurang dari 3 jam. Seperti apa ini:106
sumber
Dari FAQ Komputasi Polihedral Komei Fukuda :
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."
sumber