Misalkan saya memiliki 2D jala terdiri dari non-overlapping segitiga , dan satu set poin { p i } M i = 1 ⊂ ∪ N k = 1 T K . Apa cara terbaik untuk menentukan di mana segitiga masing-masing titik terletak?
Sebagai contoh, pada gambar berikut ini kita memiliki , p 2 ∈ T 4 , p 3 ∈ T 2 , jadi saya ingin fungsi f yang mengembalikan daftar f ( p 1 , p 2 , p 3 ) = [ 2 , 4 , 2 ] .
Matlab memiliki fungsi pointlocation yang melakukan apa yang saya inginkan untuk jerat Delaunay, tetapi gagal untuk jerat umum.
Pikiran pertama saya (bodoh) adalah, untuk semua node , loop melalui semua segitiga untuk mencari tahu di mana segitiga p i berada. Namun, ini sangat tidak efisien - Anda mungkin harus mengulangi setiap segitiga untuk setiap titik, jadi ini bisa membuat berfungsi.
Pikiran saya berikutnya adalah, untuk semua poin , menemukan node mesh terdekat melalui pencarian tetangga terdekat, kemudian melihat melalui segitiga yang melekat pada node terdekat. Dalam kasus ini, pekerjaannya adalah , di mana adalah jumlah maksimum segitiga yang melekat pada setiap simpul dalam mesh. Ada beberapa masalah yang dapat dipecahkan tetapi menyebalkan dengan pendekatan ini,
- Ini membutuhkan penerapan pencarian tetangga terdekat yang efisien (atau menemukan perpustakaan yang memilikinya), yang bisa menjadi tugas tidak trivial.
- Membutuhkan menyimpan daftar yang segitiga dilampirkan ke setiap node, yang kode saya saat ini tidak diatur untuk - saat ini hanya ada daftar koordinat simpul dan daftar elemen.
Secara keseluruhan tampaknya tidak elegan, dan saya pikir harus ada cara yang lebih baik. Ini pasti masalah yang banyak muncul, jadi saya bertanya-tanya apakah ada yang bisa merekomendasikan cara terbaik untuk mendekati menemukan apa segitiga dalam node, baik secara teoritis atau dalam hal perpustakaan yang tersedia.
Terima kasih!
sumber
Saya tidak yakin solusi Anda sebenarnya benar. Pertimbangkan situasi di mana Anda memiliki simpul-simpul ini:
Ada segitiga ABC dan ACD. Sekarang B adalah titik terdekat dengan titik asal, tetapi titik asal dalam segitiga ACD, yang tidak mengandung B.
Saya akan mempertimbangkan opsi untuk membangun quadtree yang berisi segitiga sendiri. Yaitu, Anda memiliki pohon kuaterner yang menyimpan di setiap node (yang sesuai dengan kotak pembatas):
sumber
CGAL menangani triangulasi dan lokasi titik (dan lebih banyak lagi). Secara khusus, modul triangulasi 2D dapat melakukan apa yang Anda inginkan.
sumber