Menemukan titik segitiga mana yang ada

16

Misalkan saya memiliki 2D jala terdiri dari non-overlapping segitiga , dan satu set poin { p i } M i = 1N k = 1 T K . Apa cara terbaik untuk menentukan di mana segitiga masing-masing titik terletak?{Tk}k=1N{halsaya}saya=1M.k=1NTK

Sebagai contoh, pada gambar berikut ini kita memiliki , p 2T 4 , p 3T 2 , jadi saya ingin fungsi f yang mengembalikan daftar f ( p 1 , p 2 , p 3 ) = [ 2 , 4 , 2 ] .hal1T2hal2T4hal3T2ff(hal1,hal2,hal3)=[2,4,2]

masukkan deskripsi gambar di sini

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.halsayahalsayaHAI(NM.)

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,halsayaHAI(SebuahM.lHaig(N))Sebuah

  • 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!

Nick Algeria
sumber

Jawaban:

16

Metode hopping tepi acak yang biasa harus bekerja. Pada dasarnya, mulailah dengan sembarang segitiga dari jala, kemudian tentukan sisi mana dari titik target yang terletak di sisi yang berlawanan. Yaitu, tentukan tepi mana, ketika diperpanjang ke garis, pisahkan titik dari bagian dalam segitiga. Ketika ada dua kemungkinan, pilih satu secara acak, dan pertimbangkan segitiga yang berdekatan dengan tepi bersama itu, dan ulangi. Pengacakan harus membuat metode ini menyatu dengan probabilitas 1 untuk triangulasi Delaunay, dan saya tidak bisa memikirkan alasan mengapa metode ini tidak akan berfungsi untuk triangulasi acak.

Sunting : Saya harus menambahkan bahwa hopping tepi harus dengan konstanta yang masuk akal untuk satu titik, jadi itu akan menjadi O ( M log N ) untuk poin M. Namun, jika Anda mengurutkan poin berdasarkan lokalitas (seperti menggunakan urutan kurva Hilbert terlebih dahulu), Anda dapat menginisialisasi setiap kueri baru dengan segitiga dari kueri sebelumnya, untuk lebih mengurangi runtime (saya bukan teoretikus CS jadi saya bisa ' t memberitahu Anda apa yang besar-O akan ada di sana)HAI(catatanN)HAI(M.catatanN)M.

Sunting2 : Ditemukan PDF ini menjelaskan skema "berjalan" yang dijamin akan berakhir, dan meninjau pendekatan yang lebih naif.

Alternatif lain untuk menggunakan quadtrees adalah menggunakan Triangulation Hierarchy. Lihat Olivier Devillers. Peningkatan triangulasi Delaunay acak inkremental. Di Proc. Annu ke-14. ACM Sympos. Komputasi. Geom., Halaman 106-115, 1998. Ini bekerja paling baik untuk triangulasi Delaunay, tetapi juga bisa bekerja untuk non-Delaunay.

Pada dasarnya apa pun yang Anda lakukan untuk mempercepat lokasi titik akan memerlukan pembangunan struktur data tambahan. Dalam kasus quadtrees atau subdivisi spasial lainnya, Anda perlu membangun pohon subdivisi. Dalam kasus hopping-tepi, Anda perlu membangun struktur topologi yang berdekatan dengan segitiga. Hirarki triangulasi juga membutuhkan pembangunan pohon triangulasi yang lebih kasar.

Victor Liu
sumber
Victor - apakah Anda tahu kode sumber terbuka apa pun yang menerapkan pendekatan edge-hopping? Sepertinya itu bisa menjadi solusi yang sangat baik untuk kasus saya. (model pelacakan partikel didorong oleh bidang saat ini di grid mesh traingualr) -Terima kasih
Chris Barker
Saya punya kode untuk ini dan saya bisa mengirimkannya kepada Anda; itu dalam C / C ++. Belum punya waktu untuk membersihkannya dan mempostingnya di Github. Saya harus menulis ini setidaknya dua kali dalam hidup saya, sekali dengan struktur data setengah, lagi dengan quadedge, tetapi dapat dengan mudah digunakan ketika mereka tidak tersedia dan Anda perlu membangun struktur topologi sendiri. Lihat halaman profil saya untuk situs web saya, di mana Anda dapat menemukan info kontak. Kita dapat membahas ini lebih lanjut secara offline.
Victor Liu
Saya hampir selesai mengimplementasikan ini di matlab menggunakan pemesanan kurva Hilbert dan walk segitiga acak. Ini kode penelitian: tidak dioptimalkan, tidak didokumentasikan, dll, tetapi masih cukup cepat - saya bisa memberikan kode jika Anda tertarik.
Nick Alger
2
Tentang: "" "edge hopping harus O (logN)" "" Saya tidak melihat itu. Misalnya, dalam kasus patologis strip segitiga panjang besar (seperti saluran sempit hanya pada lebar segitiga), pada kasus terburuk, Anda harus melompat dari satu segitiga ke yang berikutnya sampai ke akhir. Dalam kasus rata-rata, setengah jalan. Jadi, jika Anda menggandakan jumlah segitiga, itu akan menjadi O (N) Dalam kasus yang lebih normal dari susunan persegi-ish segitiga, saya berharap O (sqrt (N)). Atau apakah saya melewatkan sesuatu? -Chris
Chris Barker
@ Chris - Selamat datang di scicomp! Sebagai bagian dari scicomp's housekeeping, saya telah memigrasikan jawaban Anda dan percakapan berikutnya sebagai komentar atas jawaban Victor. Kami menantikan partisipasi Anda di situs ini.
Aron Ahmadia
8

Saya tidak yakin solusi Anda sebenarnya benar. Pertimbangkan situasi di mana Anda memiliki simpul-simpul ini:

  • A: (-3, 1)
  • B: (0, 2)
  • C: (3, 1)
  • D: (0, -5)

Ada segitiga ABC dan ACD. Sekarang B adalah titik terdekat dengan titik asal, tetapi titik asal dalam segitiga ACD, yang tidak mengandung B.

HAI(NM.)

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):

  • Koordinat di mana kotak itu dipecah, atau sebagai alternatif, kotak pembatas dari empat subtrees;
  • Pointer ke sub pohon;
  • Himpunan segitiga yang jatuh sepenuhnya dalam kotak pembatas dari persegi panjang ini, tetapi tidak sepenuhnya dalam salah satu dari empat subtree. Dengan kata lain, segitiga yang bersinggungan dengan salah satu dari dua segmen garis yang membagi quadtree.

nncatatannHAI(NM.)

Erik P.
sumber
Hmm kamu benar. Di sisi lain, jika triangulasi adalah Delaunay, saya pikir tetangga terdekat akan bekerja. Ini terlalu membatasi untuk apa yang saya coba lakukan, tetapi dalam kasus Delaunay pertimbangkan diagram Voronoi ganda - sel Voronoi adalah himpunan titik yang paling dekat dengan sebuah node, dan tepi segitiga delaunay semuanya memenuhi tepi Voronoi Sel-sel pada sudut kanan, jadi setiap titik harus dalam segitiga yang terhubung ke simpul terdekatnya. Saya bertanya-tanya apakah ini bagaimana fungsi pointLocation matlab bekerja di bawah tenda ..?
Nick Alger
1

CGAL menangani triangulasi dan lokasi titik (dan lebih banyak lagi). Secara khusus, modul triangulasi 2D dapat melakukan apa yang Anda inginkan.

Ronaldo Carpio
sumber