Perpustakaan Perangkat Lunak Delaunay Tesselation N-dimensional

Saya memiliki satu set titik / node yang diketahui berjarak tidak teratur dalam ruang N-Dimensi (N> = 2), dan saya ingin cara untuk menghasilkan triangulasi Delaunay dari titik-titik ini, dan mengembalikan elemen yang sesuai.

Apakah ada perpustakaan meshing yang ada yang akan melakukan triangulasi ND Delaunay?

(Saya melakukan ini karena saya ingin menggunakan elemen bertautan sebagai dasar untuk interpolasi linier di titik mana pun di ruang. Dimensi saya saat ini ditangani oleh kelas C ++ yang digabungkan dengan dimensi jika itu membuat perbedaan dengan saran ...)

computational-geometry high-dimensional mesh-generation delaunay-triangulation unstructured-mesh keajaiban
sumber

Hai, keajaiban, dan selamat datang di scicomp! Anda mungkin tertarik dengan pertanyaan ini: scicomp.stackexchange.com/questions/770/…

Paul

Terima kasih untuk tautannya, saya berharap untuk tidak menulis mesher saya sendiri. Tetgen (untuk 3D) berjalan ke banyak baris kode. Sepertinya masalah yang harus dipecahkan berkali-kali.

mirams

pertanyaan populer ... juga scicomp.stackexchange.com/questions/7664/…

clipper

Triangulasi delaunay biasanya berasal dari lambung cembung di ruang dimensi yang lebih tinggi. Lihat komentar qhull di bawah ini.

meawoppl

3D tidak terlalu sulit, tetapi untuk 4D sangat sulit saat memperbaiki, saya mengajukan pertanyaan tentang MathOverflow, tetapi belum ada jawaban: mathoverflow.net/questions/130878/…

Shuhao Cao

Jawaban:

Saya pikir Anda bisa melakukan ini menggunakan perangkat lunak cembung cembung (misalnya QHull) melalui algoritma pengangkatan. Paling tidak, dokumentasi perintah "delaunayn" matlab tampaknya mengindikasikan hal yang sama.

rchilton1980
sumber

Diuji 4D, dan itu tampaknya berfungsi dengan baik di QHull (saya menggunakannya via scipy.spatial dalam python).

Ethan Coon

Anda tidak akan mengalahkan qhull. Saya telah menggunakan melalui Scipy juga hingga 6 dimensi.

meawoppl

Hmmm - ini dari qhull.org/news/qhull-news.html tidak ideal: "Semua pengguna dalam 3-d dan lebih tinggi, opsi 'Qt' tidak menghasilkan triangulasi yang sesuai untuk aspek yang berdekatan, non-sederhana. Misalnya, jika Anda memiliki array reguler, 3-d dari situs input, triangulasi Delaunay mereka terdiri dari kubus.Pilihan 'Qt' akan melakukan triangulasi setiap kubus menjadi tetrahedra.Dalam setiap kubus, triangulasi konsisten, tetapi tidak harus konsisten antara kubus yang berdekatan [C. Bertoglio; C. de Visser]. Cara memperbaiki masalah ini tidak diketahui. " Layak dicoba, saya akan melihat bagaimana saya melanjutkan.

mirams

Fitur ini sepertinya tersedia di CGAL

Juan M. Bello-Rivas
sumber

Ini juga terlihat bagus. Saya akan mencoba Qhull dan ini. Terima kasih atas sarannya.

mirams

Saya juga menemukan distmesh di Matlab yang tampaknya dapat melakukan ini:

Beranda Distmesh

Itu tesselations untuk jerat elemen hingga (melalui QHull) tetapi dengan antarmuka yang bagus untuk mendefinisikan area / permukaan berdasarkan fungsi jarak. Lebih baik untuk kasus-kasus di mana Anda ingin mendefinisikan permukaan secara matematis dan tidak keberatan di mana node internal berada.

keajaiban
sumber