Metode interpolasi yang efisien untuk grid yang tidak terstruktur?

12

Saya ingin mengetahui metode yang baik untuk menginterpolasi data antara dua grid yang tidak terstruktur, di mana satu grid adalah versi yang lebih kasar dari yang lain.

Efisiensi sangat penting bagi saya karena saya sedang memecahkan masalah PDE sementara di mana saya perlu mentransfer data antar grid pada setiap langkah waktu dari solusi.

Saya berpikir tentang menggunakan kd-tree untuk mencari simpul terdekat dari suatu titik, kemudian saya akan menggunakan fungsi bentuk elemen tersebut (simulasi FEM) untuk menginterpolasi data. Apakah ini solusi yang baik? Apakah ada yang lebih baik?

Apakah Anda juga tahu perpustakaan yang kuat dan dapat diandalkan di C / C ++ untuk tugas ini?

* Saya tahu ada pertanyaan serupa, tetapi meminta metode yang paling akurat pada grid terstruktur.

interpolation Bernardo MR
sumber

lihat T&J ini, saya mengumpulkan banyak metode open-source untuk ini: scicomp.stackexchange.com/questions/19137/…

denfromufa

6

Grid tidak terstruktur memiliki tempatnya.

Anda mungkin ingin melihat Kerangka Pemodelan Sistem Bumi (ESMF). Mereka memiliki beberapa kode untuk grid-ulang - khusus untuk tujuan ini - dan mereka telah melakukan beberapa hal bagus dengan kode paralel juga. Seluruh sistem dirancang untuk beberapa model, jadi mungkin ada hal berguna lainnya di sana.

Beberapa catatan lain:

"tidak ada cara untuk melakukan ini secara efisien untuk sejumlah besar poin"

baik, efisien adalah hal yang relatif - setelah Anda mendapatkan grid dalam struktur pohon, Anda dapat mencarinya di O (logn), yang bisa sangat cepat, meskipun bukan O (1), seperti mencari grid biasa adalah.

Juga, sepertinya interpolasi perlu dilakukan pada setiap langkah waktu, jika grid tidak beradaptasi, maka pemetaan dari satu grid ke yang lain tetap konstan. Jadi, Anda dapat menghitung pemetaan itu (yaitu elemen mana di setiap kisi yang sesuai dengan elemen mana di yang lain) dengan cara apa pun yang nyaman, simpan, dan kemudian Anda tidak perlu menghitungnya lagi (sampai kisi-kisi berubah).

Yang membuat Anda dengan kode interpolasi - di mana Anda ingin menyeimbangkan akurasi dengan kinerja - interpolasi linier sederhana di seluruh segitiga cepat, dan mungkin cukup baik.

"Saya berpikir tentang menggunakan kd-tree untuk mencari simpul terdekat dari titik tertentu, maka saya akan menggunakan fungsi bentuk elemen itu"

ingat bahwa simpul terdekat tidak membuat Anda elemen - jadi Anda akan ingin melakukan sedikit lebih banyak untuk menemukan elemen yang Anda inginkan. Salah satu opsi adalah menggunakan rtree sebagai gantinya, yang menyimpan / mencari dengan membatasi kotak - Anda akan mendapatkan lebih dari satu elemen dengan setiap pencarian, tetapi Anda kemudian dapat memeriksa mana yang benar secara langsung.

Chris Barker
sumber

Ini terlihat bagus. Saya tidak perlu mengadaptasi jerat, sehingga pemetaan dari satu kotak ke yang lain akan dilakukan hanya sekali. Terima kasih atas tip tentang struktur data r-tree.

Bernardo MR

1

O (N)

$O(N)$

O (\log N)

$O(\log N)$

7

Jika saya memahami Anda dengan benar, Anda ingin mengisi nilai dari kisi yang lebih halus dengan menginterpolasi kisi yang lebih kasar. Salah satu cara untuk melakukan interpolasi linear pada grid yang tidak terstruktur adalah dengan triangulasi Delaunay (ini adalah bagaimana griddata dan TriScatteredInterp Matlab diimplementasikan). Setelah membangun triangulasi titik-titik grid Anda, interpolasi bermuara ke menemukan segitiga yang mengandung titik target, menghitung koordinat barycentric, dan menggunakan nilai fungsi pada simpul untuk menghitung nilai yang diinterpolasi. CGAL dapat membangun triangulasi n-dimensi (untuk n medium), dan juga memiliki modul interpolasi 2d bawaan .

Ronaldo Carpio
sumber

Iya. Tapi saya juga ingin "menyuntikkan" nilai-nilai dari grid halus ke dalam grid kasar juga, itu sebabnya saya mengatakan transfer.

Bernardo MR

3

Inilah yang saya lakukan saat ini, kecuali saya mentransfer nilai fungsi pada titik quadrature, bukan node. Saya menerapkan teknik yang dijelaskan dalam jawaban yang dipilih untuk pertanyaan saya di sini: Menemukan titik segitiga mana yang ada .

$A$ $B$ $A$ $B$

$B$ $p_i$ $A$
$p_i$
$A$ $A$
$A$ $p_1$ $p2$ $p3$ $A$

$N$ $M$ $A$ $O(N \sqrt{M})$ $O(max(N,M))$

Nick Algeria
sumber

2

Ini adalah jenis pekerjaan yang Anda benar-benar ingin hindari jerat tidak terstruktur karena tidak ada cara untuk melakukan ini secara efisien untuk sejumlah besar poin. Anda harus mempertimbangkan menggunakan jerat yang setidaknya terkait dengan masing-masing. Sebagai contoh, jika keduanya diperoleh dari penyempurnaan hirarkis dari mesh kasar, maka Anda dapat secara relatif mudah dan efisien mencari tahu di mana titik interpolasi dari satu mesh terletak di mesh lainnya.

Wolfgang Bangerth
sumber

Saya pikir itu mungkin pilihan terbaik (hierarki kisi). Jika ini masalahnya, apakah Anda tahu struktur data yang baik, atau metode spesifik yang digunakan?

Bernardo MR

Ya, jerat hierarkis semuanya disimpan sebagai quad / oct-tree (jika mereka mulai pada sel kasar tunggal) atau hutan pohon-pohon tersebut (jika mesh kasar memiliki lebih dari satu sel).

Wolfgang Bangerth

Metode interpolasi yang efisien untuk grid yang tidak terstruktur?

Jawaban: