Optimalisasi algoritma untuk pengecekan kondisi Delaunay melalui persamaan lingkaran berbatas dan penerapannya
- Pengolahan citra ,
- Pemrograman
Saya akan memberi tahu Anda rahasia cara cepat memeriksa kondisi Delaunay untuk dua segitiga.
Sebenarnya, pengoptimalan itu sendiri dijelaskan sedikit lebih rendah (lihat "Pengoptimalan algoritme untuk memeriksa kondisi Delaunay melalui persamaan lingkaran yang dibatasi"), tetapi saya akan memberi tahu Anda tentang semuanya secara berurutan.
Dalam kasus saya, triangulasi digunakan dalam penelusuran gambar untuk membagi bidang menjadi sektor-sektor primitif (segitiga). Seperti yang Anda ketahui, itu juga dibagi menjadi beberapa tahap: penyesuaian, deteksi batas, melewati batas, menyapu kontur. Ini adalah cara yang paling umum. Saya ingin berhenti, saya pikir, pada tahap yang paling sulit: menyapu pesawat.
Di pintu masuk
Setelah mendeteksi dan melewati batas pada output, saya mendapatkan banyak kontur eksternal. Setiap kontur yang bersentuhan memiliki warna yang berbeda. Setiap kontur tersebut juga mengandung sejumlah kontur internal yang diketahui.Jadi, dari sudut pandang "menyapu bidang", jika kita mempertimbangkan kontur luar secara terpisah, kita memiliki satu set titik, yang masing-masing memiliki satu tetangga di kanan dan kiri. Itu. semua titik ditutup dalam rantai, tidak ada satu titik "menggantung", dan masing-masing rantai berisi setidaknya 3 titik (Gambar 1).
Gambar 1
Apa yang perlu dilakukan?
Hal ini diperlukan untuk menyapu gambar dengan segitiga.Mencari
Setelah membaca buku tersebut, saya tidak menemukan satu (setidaknya satu) cara menyusun triangulasi Delaunay yang setidaknya cocok untuk kasus saya. Saya tidak mencari buku lain. Ya, dan ini sudah cukup, dia mengatur pikiranku. Akibatnya, ia menemukan "sepeda" miliknya sendiri.algoritma
1) Misalkan, sebagai permulaan, hanya ada satu urutan pada gambar yang sedang dipertimbangkan. Kemudian semuanya bermuara pada pengambilan segitiga secara berurutan. Kami mengambil titik mana pun dan mencoba membangun segitiga dengan titik-titik tetangga. Jika tidak mungkin untuk membangun segitiga (garis yang menghubungkan dua titik ini berpotongan dengan yang sudah dibangun atau garis yang melewati zona eksklusi (Gambar 2), kita pindah ke titik tetangga, katakanlah ke kanan. Saat berikutnya segitiga ditemukan, kami menambahkannya ke daftar (Gambar 3), dan titik dari mana ia dibangun dihapus (Gambar 4).
Gambar 2
Gambar 3
Gambar 4
Satu hal lagi: saat menyimpan segitiga berikutnya, perlu untuk merekam simpul dalam bypass searah jarum jam (dalam sistem koordinat kanan). Ini akan berguna di masa depan untuk mengurangi sumber daya komputasi.
2) Ulangi langkah 1 sampai kita menyapu seluruh bidang.
3) Jika ada beberapa urutan, mis. satu, dan di dalamnya ada satu atau lebih kontur internal (Gambar 1). Di sini perlu untuk mempertimbangkan setiap urutan secara terpisah. Mari kita ambil kontur dalam lainnya. Dari satu eksternal dan satu internal kami akan membuat dua kontur tunggal. Untuk melakukan ini, Anda perlu menemukan dua "port" dari satu sirkuit ke sirkuit lainnya. Kondisi untuk "pelabuhan": mereka tidak boleh berpotongan satu sama lain (mereka tidak boleh menyentuh bahkan ujungnya), mereka tidak boleh berpotongan dengan garis kontur (Gambar 5).
Gambar 5
Gambar 6
4)
Selanjutnya, Anda harus memasukkan secara bergantian semua urutan internal ke dalam urutan yang sudah terbentuk, terpisah satu sama lain (poin 3). Anda harus menggabungkan dengan yang berisi yang baru. Menurut definisi, tidak ada urutan internal yang menyentuh atau bersinggungan dengan yang lain (baik satu eksternal atau semua kemungkinan internal), sehingga semuanya akan berjalan lancar.
Setelah menemukan port (Gambar 6), mudah untuk membangun urutan baru dan melewatinya dengan poin 1 dan 2 dari algoritma saat ini (Gambar 7). 
Gambar 7
5)
Setelah tahap ke-4, kita memiliki daftar segitiga (Gambar 8). Seolah-olah kita telah mengatasi tugas, tetapi tetap membuat gambar menjadi indah: periksa pemenuhan kondisi Delaunay (Gambar 9). 
Angka 8
Gambar 9
6) Ke depan, saya akan memberi tahu Anda tentang poin keenam. Ini terdiri dari rangkaian berurutan melalui daftar segitiga yang diterima dengan poin No. 5. Pertama, kami menandai semua segitiga sebagai "kotor". Dalam setiap siklus, kami memeriksa kondisi Delaunay untuk setiap segitiga. Jika kondisi tidak terpenuhi, maka kami membangun kembali dan menandai tetangga dan segitiga saat ini sebagai "kotor". Jika kondisinya terpenuhi, maka tandai bersih. Dalam implementasi algoritma saya, setiap segitiga memiliki tautan ke tetangganya. Dalam hal ini, poin ke-6 bekerja paling cepat.
Lebih lanjut tentang tahap kelima
Sekarang, sejauh yang saya tahu, ada dua cara yang mungkin untuk menentukan apakah segitiga memenuhi kondisi Delaunay atau tidak: 1) Periksa jumlah sudut yang berlawanan. Itu harus kurang dari 180. 2) Hitung pusat lingkaran yang dibatasi dan hitung jarak ke titik ke-4. Semua orang tahu bahwa kondisi Delaunay terpenuhi jika titiknya berada di luar lingkaran yang dibatasi.Daya komputasi #1: 10 operasi perkalian/pembagian dan 13 operasi penjumlahan/pengurangan.
Daya komputasi #2: 29 perkalian/pembagian dan 24 penjumlahan/pengurangan.
Dari sudut pandang daya komputasi, yang dihitung, misalnya, dalam buku, opsi nomor 1 lebih menguntungkan. Dan dia menyadarinya, jika bukan karena ... (Gambar 10). Ternyata, setelah menerapkan metode ini pada "konveyor", ada ketidakpastian. Ini adalah pilihan ketika sudut A itu sendiri lebih besar dari 180 derajat. Itu diperlakukan dalam buku sebagai salah satu metode pribadi yang terpisah. Dan dengan ini, semua keanggunan, transparansi, dan kinerjanya menghilang. Dan juga belakangan ternyata cara no 2 bisa dioptimasi dengan sangat signifikan.
Gambar 10
Optimalisasi algoritma untuk memeriksa kondisi Delaunay melalui persamaan lingkaran terbatas
Berikut ini adalah matematika murni.Jadi kita punya:
Pemeriksaan kondisi titik M(X, Y) dengan persamaan lingkaran yang melalui titik A(x1, y1), B(x2, y2), C(x3, y3) dapat ditulis sebagai:
(a (X^2 + Y^ 2) b X + c Y − d) tanda a 0
Detailnya dapat ditemukan di buku yang sangat bagus. (Tidak, saya bukan penulisnya)
Jadi, tanda a adalah tanda arah traversal, dari awal saya bangun segitiga searah jarum jam, sehingga bisa dihilangkan (sama dengan satu).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D >= 0 
Gambar 11
Hanya bukan?
Menurut buku itu, sekali lagi,
(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0
Kami memiliki: 15 operasi perkalian/pembagian dan 14 operasi penjumlahan/pengurangan.
Terima kasih atas perhatian Anda. saya tunggu kritiknya.
Bibliografi
1. Skvortsov A.V. Triangulasi Delaunay dan Penerapannya. - Tomsk: Rumah Penerbitan Vol. un-ta, 2002. - 128 hal. ISBN 5-7511-1501-5 20 Agustus 2012 pukul 22:41Optimalisasi algoritma untuk pengecekan kondisi Delaunay melalui persamaan lingkaran berbatas dan penerapannya
Saya akan memberi tahu Anda rahasia cara cepat memeriksa kondisi Delaunay untuk dua segitiga.
Sebenarnya, pengoptimalan itu sendiri dijelaskan sedikit lebih rendah (lihat "Pengoptimalan algoritme untuk memeriksa kondisi Delaunay melalui persamaan lingkaran yang dibatasi"), tetapi saya akan memberi tahu Anda tentang semuanya secara berurutan.
Dalam kasus saya, triangulasi digunakan dalam penelusuran gambar untuk membagi bidang menjadi sektor-sektor primitif (segitiga). Seperti yang Anda ketahui, itu juga dibagi menjadi beberapa tahap: penyesuaian, deteksi batas, melewati batas, menyapu kontur. Ini adalah cara yang paling umum. Saya ingin berhenti, saya pikir, pada tahap yang paling sulit: menyapu pesawat.
Di pintu masuk
Setelah mendeteksi dan melewati batas pada output, saya mendapatkan banyak kontur eksternal. Setiap kontur yang bersentuhan memiliki warna yang berbeda. Setiap kontur tersebut juga mengandung sejumlah kontur internal yang diketahui.Jadi, dari sudut pandang "menyapu bidang", jika kita mempertimbangkan kontur luar secara terpisah, kita memiliki satu set titik, yang masing-masing memiliki satu tetangga di kanan dan kiri. Itu. semua titik ditutup dalam rantai, tidak ada satu titik "menggantung", dan masing-masing rantai berisi setidaknya 3 titik (Gambar 1).
Gambar 1
Apa yang perlu dilakukan?
Hal ini diperlukan untuk menyapu gambar dengan segitiga.Mencari
Setelah membaca buku tersebut, saya tidak menemukan satu (setidaknya satu) cara menyusun triangulasi Delaunay yang setidaknya cocok untuk kasus saya. Saya tidak mencari buku lain. Ya, dan ini sudah cukup, dia mengatur pikiranku. Akibatnya, ia menemukan "sepeda" miliknya sendiri.algoritma
1) Misalkan, sebagai permulaan, hanya ada satu urutan pada gambar yang sedang dipertimbangkan. Kemudian semuanya bermuara pada pengambilan segitiga secara berurutan. Kami mengambil titik mana pun dan mencoba membangun segitiga dengan titik-titik tetangga. Jika tidak mungkin untuk membangun segitiga (garis yang menghubungkan dua titik ini berpotongan dengan yang sudah dibangun atau garis yang melewati zona eksklusi (Gambar 2), kita pindah ke titik tetangga, katakanlah ke kanan. Saat berikutnya segitiga ditemukan, kami menambahkannya ke daftar (Gambar 3), dan titik dari mana ia dibangun dihapus (Gambar 4).
Gambar 2
Gambar 3
Gambar 4
Satu hal lagi: saat menyimpan segitiga berikutnya, perlu untuk merekam simpul dalam bypass searah jarum jam (dalam sistem koordinat kanan). Ini akan berguna di masa depan untuk mengurangi sumber daya komputasi.
2) Ulangi langkah 1 sampai kita menyapu seluruh bidang.
3) Jika ada beberapa urutan, mis. satu, dan di dalamnya ada satu atau lebih kontur internal (Gambar 1). Di sini perlu untuk mempertimbangkan setiap urutan secara terpisah. Mari kita ambil kontur dalam lainnya. Dari satu eksternal dan satu internal kami akan membuat dua kontur tunggal. Untuk melakukan ini, Anda perlu menemukan dua "port" dari satu sirkuit ke sirkuit lainnya. Kondisi untuk "pelabuhan": mereka tidak boleh berpotongan satu sama lain (mereka tidak boleh menyentuh bahkan ujungnya), mereka tidak boleh berpotongan dengan garis kontur (Gambar 5).
Gambar 5
Gambar 6
4)
Selanjutnya, Anda harus memasukkan secara bergantian semua urutan internal ke dalam urutan yang sudah terbentuk, terpisah satu sama lain (poin 3). Anda harus menggabungkan dengan yang berisi yang baru. Menurut definisi, tidak ada urutan internal yang menyentuh atau bersinggungan dengan yang lain (baik satu eksternal atau semua kemungkinan internal), sehingga semuanya akan berjalan lancar.
Setelah menemukan port (Gambar 6), mudah untuk membangun urutan baru dan melewatinya dengan poin 1 dan 2 dari algoritma saat ini (Gambar 7).
Gambar 7
5)
Setelah tahap ke-4, kita memiliki daftar segitiga (Gambar 8). Seolah-olah kita telah mengatasi tugas, tetapi tetap membuat gambar menjadi indah: periksa pemenuhan kondisi Delaunay (Gambar 9).
Angka 8
Gambar 9
6) Ke depan, saya akan memberi tahu Anda tentang poin keenam. Ini terdiri dari rangkaian berurutan melalui daftar segitiga yang diterima dengan poin No. 5. Pertama, kami menandai semua segitiga sebagai "kotor". Dalam setiap siklus, kami memeriksa kondisi Delaunay untuk setiap segitiga. Jika kondisi tidak terpenuhi, maka kami membangun kembali dan menandai tetangga dan segitiga saat ini sebagai "kotor". Jika kondisinya terpenuhi, maka tandai bersih. Dalam implementasi algoritma saya, setiap segitiga memiliki tautan ke tetangganya. Dalam hal ini, poin ke-6 bekerja paling cepat.
Lebih lanjut tentang tahap kelima
Sekarang, sejauh yang saya tahu, ada dua cara yang mungkin untuk menentukan apakah segitiga memenuhi kondisi Delaunay atau tidak: 1) Periksa jumlah sudut yang berlawanan. Itu harus kurang dari 180. 2) Hitung pusat lingkaran yang dibatasi dan hitung jarak ke titik ke-4. Semua orang tahu bahwa kondisi Delaunay terpenuhi jika titiknya berada di luar lingkaran yang dibatasi.Daya komputasi #1: 10 operasi perkalian/pembagian dan 13 operasi penjumlahan/pengurangan.
Daya komputasi #2: 29 perkalian/pembagian dan 24 penjumlahan/pengurangan.
Dari sudut pandang daya komputasi, yang dihitung, misalnya, dalam buku, opsi nomor 1 lebih menguntungkan. Dan dia menyadarinya, jika bukan karena ... (Gambar 10). Ternyata, setelah menerapkan metode ini pada "konveyor", ada ketidakpastian. Ini adalah pilihan ketika sudut A itu sendiri lebih besar dari 180 derajat. Itu diperlakukan dalam buku sebagai salah satu metode pribadi yang terpisah. Dan dengan ini, semua keanggunan, transparansi, dan kinerjanya menghilang. Dan juga belakangan ternyata cara no 2 bisa dioptimasi dengan sangat signifikan.
Gambar 10
Optimalisasi algoritma untuk memeriksa kondisi Delaunay melalui persamaan lingkaran terbatas
Berikut ini adalah matematika murni.Jadi kita punya:
Pemeriksaan kondisi titik M(X, Y) dengan persamaan lingkaran yang melalui titik A(x1, y1), B(x2, y2), C(x3, y3) dapat ditulis sebagai:
(a (X^2 + Y^ 2) b X + c Y − d) tanda a 0
Detailnya dapat ditemukan di buku yang sangat bagus. (Tidak, saya bukan penulisnya)
Jadi, tanda a adalah tanda arah traversal, dari awal saya bangun segitiga searah jarum jam, sehingga bisa dihilangkan (sama dengan satu).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D >= 0
Gambar 11
Hanya bukan?
Menurut buku itu, sekali lagi,
(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0
Kami memiliki: 15 operasi perkalian/pembagian dan 14 operasi penjumlahan/pengurangan.
Terima kasih atas perhatian Anda. saya tunggu kritiknya.
Bibliografi
1. Skvortsov A.V. Triangulasi Delaunay dan Penerapannya. - Tomsk: Rumah Penerbitan Vol. un-ta, 2002. - 128 hal. ISBN 5-7511-1501-5Untuk mengukur kualitas triangulasi yang dibangun, kami mendefinisikan dua jenis kriteria, topologi dan geometris.
Kriteria topologi didasarkan pada tetangga terdekat dari suatu titik dari suatu himpunan. Idealnya, sebuah titik memiliki 6 tetangga untuk wilayah 2D dan 12 tetangga untuk wilayah 3D. Kami memperoleh perkiraan topologi menggunakan rumus (1), di mana adalah jumlah total titik di wilayah tersebut, adalah derajat atau jumlah titik tetangga yang terhubung dengan titik internal.
Kriteria geometris didasarkan pada perbedaan antara lingkaran bertulis dan terbatas di sekitar elemen segitiga yang dihitung. Kami memperoleh perkiraan geometris menggunakan rumus (2), di mana adalah jumlah segitiga, adalah jari-jari lingkaran bertulis, adalah jari-jari lingkaran yang dibatasi.
Algoritma untuk membangun triangulasi
Ada sejumlah besar algoritma untuk membangun triangulasi. Mereka berbeda satu sama lain dalam kesulitan, kompleksitas implementasi pada komputer, dan pendekatan konstruksi. Anda dapat mempelajari lebih lanjut tentang algoritma dalam buku oleh A.V. Skvortsova. Mari kita pertimbangkan beberapa algoritma.
Salah satu yang pertama diusulkan algoritma serakah membangun triangulasi. Sebuah triangulasi Delaunay disebut serakah jika dibangun menggunakan algoritma serakah. Kompleksitas dari algoritma greedy dengan beberapa perbaikannya adalah . Karena kerumitan yang begitu besar dalam praktiknya, hampir tidak pernah digunakan. Pertimbangkan algoritma langkah demi langkah:
Langkah 1. Daftar semua segmen garis yang mungkin menghubungkan pasangan titik sumber dihasilkan dan diurutkan berdasarkan panjang segmen.
Langkah 2 Mulai dari yang terpendek, segmen-segmen tersebut secara berurutan dimasukkan ke dalam triangulasi. Jika segmen tersebut tidak berpotongan dengan segmen lain yang dimasukkan sebelumnya, maka segmen tersebut dimasukkan, jika tidak maka akan dibuang.
Perhatikan bahwa jika semua segmen yang mungkin memiliki panjang yang berbeda, maka hasil dari algoritma ini tidak ambigu, selain itu tergantung pada urutan penyisipan segmen dengan panjang yang sama.
Algoritma iteratif didasarkan pada ide yang sangat sederhana untuk secara berurutan menambahkan poin ke triangulasi Delaunay yang dibangun sebagian. Kompleksitas algoritme ini terdiri dari kerumitan menemukan segitiga, di mana sebuah titik ditambahkan pada langkah berikutnya, kerumitan membangun segitiga baru, serta kerumitan pembangunan kembali struktur triangulasi yang sesuai sebagai akibat dari hasil yang tidak memuaskan. pemeriksaan pasangan segitiga tetangga dari hasil triangulasi untuk kondisi Delaunay. Pertimbangkan algoritma langkah demi langkah:
Langkah 1. Pada tiga titik awal pertama kita membangun satu segitiga.
Langkah 2 Dalam loop untuk semua poin lainnya, lakukan langkah 3-5.
Langkah 3 Poin -th berikutnya ditambahkan ke struktur triangulasi yang sudah dibangun sebagai berikut. Pertama, intinya dilokalisasi, mis. ada segitiga (dibangun sebelumnya), di mana titik berikutnya jatuh. Atau, jika titik tersebut tidak termasuk dalam triangulasi, ada segitiga di perbatasan triangulasi yang paling dekat dengan titik berikutnya.
Langkah 4 Jika suatu titik mengenai simpul triangulasi yang dimasukkan sebelumnya, maka titik tersebut biasanya dibuang, jika tidak, titik tersebut dimasukkan ke dalam triangulasi sebagai simpul baru. Apalagi jika titik tersebut mengenai suatu sisi, maka titik tersebut dibagi menjadi dua yang baru, dan kedua segitiga yang berdekatan dengan tepi tersebut juga dibagi menjadi dua yang lebih kecil. Jika titik itu benar-benar berada di dalam segitiga apa pun, itu dibagi menjadi tiga yang baru. Jika titik berada di luar triangulasi, maka satu atau lebih segitiga dibangun.
Langkah 5 Pemeriksaan lokal dari segitiga yang baru diperoleh untuk kepatuhan dengan kondisi Delaunay dilakukan dan penataan ulang yang diperlukan dilakukan.
Saat membangun segitiga baru, dua situasi mungkin terjadi ketika titik yang ditambahkan berada di dalam segitiga atau di luarnya. Dalam kasus pertama, segitiga baru dibangun dan jumlah tindakan yang dilakukan oleh algoritma adalah tetap. Yang kedua, perlu untuk membangun segitiga tambahan di luar triangulasi saat ini, dan jumlahnya bisa sama dalam kasus terburuk? 3. Namun, tidak lebih dari segitiga yang akan ditambahkan untuk semua langkah algoritma, di mana adalah jumlah total titik awal. Oleh karena itu, dalam kedua kasus, total waktu yang dihabiskan untuk membangun segitiga adalah.
Algoritma rantai salah satu algoritma konstruksi triangulasi efisien pertama didasarkan pada prosedur regularisasi graf planar dan triangulasi poligon monoton. Kompleksitas algoritma ini adalah, di mana adalah jumlah segmen awal. Pertimbangkan algoritma langkah demi langkah:
Langkah 1. Dari himpunan segmen struktural awal, kami membentuk grafik planar terhubung (Gambar 4, a).
Langkah 2 Grafiknya teratur, mis. tepi baru ditambahkan yang tidak berpotongan dengan yang lain, sehingga setiap simpul dari graf menjadi bertetangga dengan setidaknya satu simpul di atasnya dan satu di bawahnya. Regularisasi dilakukan dalam dua lintasan menggunakan sapuan datar vertikal. Pada lintasan pertama dari bawah ke atas, kami secara berurutan menemukan semua simpul dari mana tidak ada tepi yang mengarah ke atas. Sebagai contoh, pada (Gambar 4, b) ini adalah simpul B. Menggambar garis horizontal, kita menemukan tepi terdekat dari grafik AD dan EF yang dilintasi di kiri dan kanan. Kemudian kami menemukan titik terendah dalam segiempat DEHG dan menggambar tepi dari B ke dalamnya. Demikian pula, lintasan kedua dilakukan dari atas ke bawah (Gambar 4, c). Sebagai hasil dari langkah ini, setiap area grafik planar menjadi poligon yang monoton.
Langkah 3 Setiap area grafik harus dibagi menjadi segitiga. Untuk melakukan ini, Anda dapat menggunakan algoritma penggabungan non-cembung dari dua triangulasi (Gambar 4, d).
Gambar 4. Skema operasi dari algoritma rantai triangulasi: a) - segmen awal; b - bagian dari bawah ke atas regularisasi grafik; c) - bagian dari atas ke bawah; d) - triangulasi poligon monoton
Untuk menerapkan algoritma rantai, yang terbaik adalah menggunakan struktur data di mana tepi secara eksplisit diwakili, seperti "Tepi ganda" atau "Simpul, tepi dan segitiga".
Kerugian dari algoritma rantai adalah tidak ada yang bisa dikatakan sebelumnya tentang bentuk triangulasi yang dihasilkan. Ini bukan triangulasi optimal, bukan triangulasi serakah, dan bukan triangulasi Delaunay yang dibatasi. Algoritma rantai dapat menghasilkan segitiga memanjang yang sangat panjang.
Untuk meningkatkan kualitas triangulasi yang dihasilkan, semua pasangan segitiga yang berdekatan yang tidak dipisahkan oleh tepi struktural dapat diperiksa untuk pemenuhan kondisi Delaunay dan, jika perlu, dibangun kembali. Akibatnya, triangulasi Delaunay dengan pembatasan akan diperoleh.
Model GRID adalah model sel reguler.
Misalkan sistem koordinat 
dan 
dan 
. Set pengguna 
dan langkah pengambilan sampel 
.
,
- koordinat fisik titik.
Menghitung 
dan 
,
- jaringan bit.
- nilai terkuantisasi. Nyata:
- parameter algoritma - jumlah poin, 
- beratnya. Semakin dekat titik, semakin besar bobotnya.
- derajat jarak (1 atau 2).
Faktor normalisasi: 
Bagaimana 
mendekati 1, poin yang lebih berbobot diperhitungkan.
Ini adalah metode IDW - panjang, untuk setiap t perlu menemukan tetangga. Satu set tetangga dapat ditemukan secara efisien - terdekat. Setiap titik menghasilkan "pasak" dengan ketinggian tertentu. Banyak tergantung pada ketidakteraturan pengaturan titik, untuk ini mereka mengambil 
atau 
itu. membagi menjadi sektor dan membangun di sekitar titik.
Keuntungan– kesederhanaan
Kekurangan:
------Tiket 14. Model timah. Algoritma triangulasi Delaunay ------
1) Triangulasi (timah).
Triangulasi– konstruksi fungsi dalam bentuk himpunan fungsi linier sepotong-sepotong
Triangulasi- interpolasi di dalam daerah cembung.
Triangulasi adalah graf planar yang semua sisi dalamnya segitiga; cara merepresentasikan ruang dalam bentuk segitiga yang saling berdampingan tanpa tumpang tindih. Triangulasi dibangun di atas sekumpulan titik dalam beberapa cara.
Untuk membangun triangulasi yang optimal diperlukan suatu algoritma.
Sebuah pesawat melewati 3 titik.
1) Carilah segitiga yang 
;
2)
- kami membangun persamaan pesawat.
Untuk memeriksa apakah titik-titik berada di dalam segitiga atau tidak, Anda perlu mensubstitusikan nilainya ke dalam persamaan garis - tepi segitiga. Jika semua 3 persamaan > 0, maka di dalam.
Lihat struktur:
Setiap triangulasi mengandung jumlah segitiga yang sama.
, di mana 
adalah jumlah titik internal, 
- jumlah poin.
Triangulasi serakah.
Kami menghubungkan semua titik dengan tepi, pilih minimum, tambahkan ke triangulasi. Selanjutnya, kita ambil minimum berikutnya yang tidak bersinggungan dengan yang sebelumnya, dan seterusnya. Hasilnya adalah triangulasi serakah.
triangulasi Delaunay.
Titik-titik dari segitiga lain tidak termasuk dalam lingkaran yang dibatasi di sekitar segitiga mana pun. Dibangun dalam satu cara.
Flip adalah flip tepi. Ini memungkinkan Anda untuk beralih dari triangulasi konvensional ke triangulasi Delaunay. Untuk memeriksa apakah suatu titik termasuk dalam lingkaran: gantikan jika< R, то внутри.
Kondisi Delaunay.
Persamaan lingkaran yang melalui tiga titik:
Jika kurang dari nol, maka eksternal, jika tidak - internal.
adalah kondisi Delaunay.
Algoritma untuk membangun triangulasi Delaunay:
1) Dalam penyelidikan menambahkan poin adalah algoritma iteratif sederhana:
Ada satu set 
tambahkan ke segitiga, konstruksi dilakukan 
partisi segitiga 
pembangunan kembali. Pada tahap nol, kami menambahkan 3-4 poin fiktif yang jelas menutupi amplop kami, semua poin ada di dalam. Setelah kita lempar satu titik, lihat segitiga mana yang terkena, bagi menjadi 3, untuk setiap segitiga kita periksa kondisi Delaunay dan balikkan ujungnya. Jumlah rata-rata pembangunan kembali adalah tiga.
Kompleksitas teoritis 
2) Metode percepatan. Berdasarkan poin yang bergantung secara statistik. Segitiga benih adalah segitiga di mana titik sebelumnya jatuh. Kemudian kami menghubungkan dua titik - yang sebelumnya dan yang baru.
Kami berpindah dari poin pertama ke poin lainnya.
(Pengembangan dan Implementasi Algoritma untuk Triangulasi Volume Terkendala: Algoritma Iteratif
Pracetak, Inst. aplikasi Math., Akademi Sains Rusia)
Galanin M.P., Shcheglov I.A.
(M.P.Galanin, I.A.Sheglov)
IPM mereka. M.V. Keldysh RAS
Moskow, 2006
Pekerjaan ini didukung oleh Yayasan Rusia untuk Riset Dasar (Nomor Proyek 06-01-00421)
anotasi
Metode iteratif untuk diskritisasi tiga dimensi dari domain spasial (konstruksi jerat tetrahedral) dipertimbangkan: metode koreksi batas, metode berdasarkan kriteria Delaunay, dan metode kelelahan. Varian algoritma untuk masing-masing metode ini diberikan. Fitur membangun grid dalam domain yang kompleks dibahas.
Abstrak
Tiga keluarga utama dari algoritma iteratif untuk triangulasi volume sederhana bebas dan dibatasi dijelaskan: koreksi batas (termasuk algoritma "octree"), metode berbasis Delaunay dan pendekatan depan yang maju. Untuk setiap jenis metode, contoh algoritma diberikan.
1. Perkenalan 3
2. Metode koreksi batas4
2.1 Konstruksi jaringan primer4
2.2 Koreksi jaringan primer6
3. Metode berdasarkan kriteria Delaunay9
3.1 Membangun triangulasi Delaunay pada himpunan poin tertentu 12
3.2. Triangulasi Delaunay dengan pembatasan17
3.3 Fitur implementasi teknis algoritma berdasarkan
Kriteria penundaan
22
4. Metode kelelahan23
4.1 Contoh algoritma kelelahan26
Referensi3 0
Di antara dua kelas metode triangulasi - langsung dan berulang - yang terakhir memiliki universalitas yang cukup dan oleh karena itu, tidak seperti yang langsung, dapat digunakan untuk melakukan triangulasi daerah dengan bentuk yang agak sewenang-wenang. Fleksibilitas ini datang dengan biaya konsumsi sumber daya yang jauh lebih tinggi dan implementasi metode yang lebih padat karya dalam algoritme tertentu.
Saat ini, sejumlah besar paket perangkat lunak telah dikembangkan berdasarkan satu atau lain metode berulang yang mengimplementasikan konstruksi grid (sebagian atau seluruhnya) dalam mode otomatis. Pada dasarnya, paket-paket ini bersifat komersial, yang cukup dibenarkan mengingat upaya yang dihabiskan untuk pembuatannya, karena ruang tiga dimensi memiliki sejumlah fitur tidak menyenangkan yang secara signifikan mempersulit kehidupan pengembang.
Mesh yang dibangun dengan metode iteratif biasanya tidak terstruktur dan tidak homogen. Ketidakteraturan disebabkan oleh fakta bahwa topologi grid terbentuk dalam proses konstruksi, dan oleh karena itu secara alami dapat bervariasi bahkan dalam subdomain yang sama. Untuk alasan yang sama, homogenitas, jika bisa muncul, hanya terjadi secara kebetulan.
Karena tidak ada yang dapat dikatakan tentang struktur masa depan sebelum mesh dibangun, kualitasnya juga tidak dapat dijamin. Seringkali, mesh yang dibangun dapat ditingkatkan secara signifikan menggunakan salah satu dari banyak teknik optimasi. Kemungkinan ini biasanya tidak diabaikan, karena waktu yang dihabiskan untuk pengoptimalan, sebagai suatu peraturan, secara signifikan lebih sedikit daripada waktu yang dihabiskan untuk membangun.
Tujuan dari pekerjaan ini adalah untuk meninjau dan mengklasifikasikan metode yang ada untuk membangun jerat tetrahedral dalam domain tiga dimensi. Mengingat banyaknya informasi, hanya apa yang disebut "metode berulang" yang dipertimbangkan di bawah ini. Metode langsung dijelaskan dalam .
Pekerjaan ini didukung sebagian oleh Yayasan Rusia untuk Riset Dasar (Nomor Proyek 06-01-00421).
Beras. 11. Triangulasi domain yang mewakili gabungan dodecahedron dan icosahedron (triangulasi Delaunay dengan batasan)
Kualitas mata jaring yang dibangun dengan metode ini berada pada tingkat rata-rata (tetrahedra di dekat batas dapat memiliki bentuk yang sangat buruk), sehingga salah satu metode optimasi biasanya juga digunakan.
Dalam karya B. Joe, varian lain dari algoritma diusulkan yang tidak menggunakan poin tambahan dan sepenuhnya didasarkan pada transformasi lokal yang mirip dengan "perdagangan".
4) volume tetrahedron tidak lebih dari maksimum yang diijinkan ().
Dari semua tetrahedra () tetrahedron dengan kualitas terbaik dipilih dan transisi ke langkah 5 dibuat; jika tidak ada tetrahedra yang memenuhi kondisi yang ditunjukkan, maka transisi ke langkah 4 dilakukan.
4. Ada suatu titik di dalam wilayah yang masih tak habis-habisnya sehingga:
1) tetrahedron () memenuhi semua kondisi paragraf 3;
2) dalam bola tidak ada titik jarak jauhF(ini mencegah node ditempatkanp terlalu dekat dengan wajah dan simpul dari tetrahedra yang ada).
Varian dari algoritma pencarian nodepdidiskusikan di bawah.
5. Hapus semua simpulF, jatuh di dalam (dan pada batas) dari tetrahedron yang terbentuk. Kemudian bagian depan diperbarui sesuai dengan skema berikut: setiap wajah tetrahedron yang terbentuk dipertimbangkan dan
1) jika wajah adalah wajah depan, maka dihapus dari depan;
2) jika wajah BUKAN wajah depan, itu ditambahkan ke depan.
6. Jika masih ada poin yang tidak terhapusFatau (yang setara) bagian depan tidak kosong (yaitu, wilayah belum sepenuhnya habis), transisi ke langkah 1 dilakukan, jika tidak, proses selesai.
Jadi susunannyaFdigunakan untuk beberapa tujuan sekaligus: untuk memperkirakan nilai sudut padat, untuk mengontrol kebenaran konstruksi, dan untuk mengontrol penempatan node baru. Juga arrayFberguna untuk menunjukkan kemajuan. Rasio jumlah poin yang dihapus selama operasi algoritmaFke jumlah awal poin yang adaFsebenarnya menunjukkan berapa banyak area yang sudah habis.
Mari kembali ke pertanyaan menemukan koordinat simpul baru untuk membangun tetrahedron (item 4 dari algoritma yang dijelaskan). Biarkan tiga node - diberikan.
1. Pada langkah pertama, kami menemukan - pusat massa segitiga (sebagai rata-rata aritmatika dari koordinat simpulnya) dan unit yang normal terhadap bidang wajah (melalui produk vektor yang dinormalisasi).
2. Selanjutnya, pendekatan pertama ditentukan untuk jarak dari ke titik yang diinginkanp (H), berdasarkan volume maksimum tetrahedron: . Perhatikan bahwa area wajahSsebenarnya ditemukan pada langkah sebelumnya (hasil perkalian silang dua sisi sama dengan dua kali luas permukaan), dan volume maksimum ditentukan oleh nilai fungsi kontrol.
3. Intinya dicentang. Jika tetrahedron () memenuhi semua persyaratan, lanjutkan ke langkah 6, jika tidak lanjutkan ke langkah 4.
4. Intinya dicentang. Jika tetrahedron () memenuhi semua persyaratan, lanjutkan ke langkah 6, jika tidak lanjutkan ke langkah 5.
5. Percaya dan lanjutkan ke langkah 3.
6. Node yang diinginkan ditemukan.
Perhatikan bahwa dalam 99% kasus, titik yang diinginkan terletak pada 1 atau 2 iterasi dari algoritma ini.
Dalam algoritma kelelahan yang dijelaskan di atas, satu tetrahedron dihilangkan dari wilayah pada setiap langkah. Karyawan NASA Sh. Pirzade ( Shahyar Pirzadeh ) mengusulkan versi lain dari algoritme, di mana seluruh lapisan tetrahedra dihapus dari wilayah tersebut sekaligus (yaitu, pada setiap iterasi, tetrahedra segera dibangun untuk semua muka depan saat ini) . Berlawanan dengan harapan, varian ini tidak secara signifikan mempercepat proses konstruksi (karena semua tetrahedra baru masih perlu diperiksa kebenarannya), tetapi menghilangkan kebutuhan untuk mencari wajah yang paling cocok untuk membangun tetrahedron. Namun, ini lebih merupakan minus daripada plus, karena karena fitur ini, varian Pirzade kurang dapat diandalkan dan dapat gagal di area yang rumit secara geometris. Pada saat yang sama, ini menunjukkan hasil yang baik di area yang relatif sederhana.
Mesh yang dibangun dengan metode kelelahan, sebagai suatu peraturan, memiliki kualitas yang baik, dan optimalisasi posisi node selanjutnya memberikan peningkatan kualitas tambahan. Kesimpulannya, kami mencatat bahwa metode kelelahan paling efektif jika triangulasi batas area awalnya ditetapkan. Ini adalah perbedaan utama mereka dari metode berdasarkan kriteria Delaunay, di mana situasinya berbanding terbalik.
Bibliografi
1. Shaydurov V.V. Metode Elemen Hingga Multigrid. - M., Nauka, 1989. - 288s.
2. Skvortsov A.V. Ikhtisar algoritma untuk membangun triangulasi Delaunay // , 2002, №3, c. 14-39.
3. Skvortsov A.V. Algoritma untuk membuat triangulasi dengan batasan // Metode dan pemrograman komputasi, 2002, №3, c. 82-92.
4. I.Babushka, W.C. Rheinboldt. Estimasi Kesalahan A-posteriori untuk Metode Elemen Hingga // Int. J. Nomor. sabu Ind., Jil. 12, hal. 1597-1615, 1978.
5. TJ Tukang roti. Pembuatan Mesh Otomatis untuk Region Tiga Dimensi yang Kompleks Menggunakan Triangulasi Delaunay Terkendala // Rekayasa Dengan Komputer, Springer-Verlag, No. 5, hal. 161-175, 1989.
6. M. Bern, D. Eppstein. Pembuatan Mesh dan Triangulasi Optimal // Komputasi dalam Geometri Euclidean, World Scientific Publishing Co., hal. 23-90, 1995.
7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Representasi Ringkas Jaring Sederhana Dalam Dua dan Tiga Dimensi // Prosiding Meja Bundar Meshing Internasional ke-12, Sandia National Laboratories, hal.135-146, Sep. 2003.
8. H. Borouchaki, S.H. lihat Triangulasi Delaunay Cepat Dalam Tiga Dimensi // Metode Komputer Dalam Mekanika Dan Teknik Terapan, Elsevier, Vol. 128, hal. 153-167, 1995.
9. E.K. Buratynski. Generator Mesh Tidak Terstruktur Tiga Dimensi untuk Batas Internal Sewenang-wenang // Pembangkitan Grid Numerik dalam Mekanika Fluida Komputasi, Pers Pineridge, hal. 621-631, 1988.
10. PR Cavalcanti, U.T. halo. Triangulasi Delaunay Terkendala Tiga Dimensi: Pendekatan Minimalis // Prosiding Meja Bundar Meshing Internasional ke-8, hal. 119-129, 1999.
11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Triangulasi Delaunay Dalam Tiga Dimensi Dengan Aritmatika Presisi Hingga // Desain Geometris Berbantuan Komputer, Belanda Utara, No. 9, hal. 457-470, 1992.
12. H.N. Djidjev. Metode Force-Directed Untuk Menghaluskan Mesh Segitiga Dan Tetrahedral Tidak Terstruktur // Prosiding Meja Bundar Meshing Internasional ke-9, Laboratorium Nasional Sandia, hal. 395-406, Oktober 2000.
13. L.Durbeck. Evaporasi: Teknik Untuk Memvisualisasikan Kualitas Mesh // Prosiding Meja Bundar Meshing Internasional ke-8, South Lake Tahoe, CA, AS, hal. 259-265, Oktober 1999.
14. D.A. bidang. Triangulasi Laplacian Smoothing Dan Delaunay // , vol. 4, hal. 709-712, 1988.
15. P.J. Frey, H. Borouchaki, P.-L. George. Tetrahedralisasi Delaunay Menggunakan Pendekatan Advancing-Front // Prosiding Meja Bundar Meshing Internasional ke-5, Laboratorium Nasional Sandia, hal. 31-46, Oktober 1996.
16. LA. Freitag, C.Ollivier-Gooch. Perbandingan Teknik Peningkatan Tetrahedral Mesh // Prosiding Meja Bundar Meshing Internasional ke-5, Laboratorium Nasional Sandia, hal. 87-106, Oktober 1996.
17. LA. Freitag, C. Ollivier-Gooch Peningkatan Tetrahedral Mesh Menggunakan Swapping dan Smoothing // , vol. 40, hal. 3979-4002, 1995.
18. LA. Freitag, C.Ollivier-Gooch. Pengaruh Kualitas Mesh Terhadap Efisiensi Solusi // Prosiding Meja Bundar Meshing Internasional ke-6, Laboratorium Nasional Sandia, hal.249, Oktober 1997.
19. P.L. George. TET MESHING: Konstruksi, Optimalisasi, dan Adaptasi // Prosiding 8thMeja Bundar Mesh Internasional, hal.133-141, 1999.
20. N.A. Golias, T.D. Tsibuki. Pendekatan untuk Memperbaiki Mesh Tetrahedral Tiga Dimensi Berdasarkan Transformasi Delaunay // , John Wiley, No. 37, hal.793-812, 1994.
21. C. Hazlewood. Mendekati Tetrahedralisasi Terkendala // Desain Geometris Berbantuan Komputer, vol. 10, hal. 67–87, 1993.
22. B.Jo. Jerat Segitiga Delaunay dalam poligon Cembung, SIAM J Sci. status komputasi., Jil. 7, hal. 514-539, 1986.
23. B.Jo. Konstruksi Triangulasi Delaunay Tiga Dimensi Menggunakan Transformasi Lokal // Desain Geometris Berbantuan Komputer, Jil. 8, hal. 123-142, 1991.
24. B.Jo. Konstruksi Triangulasi Peningkatan Kualitas Tiga Dimensi Menggunakan Transformasi Lokal // Siam J.Sc. Hitung., vol. 16, hal. 1292-1307, 1995.
25. R.W. Lewis, Yao Zheng, D.T. Getin. Pembuatan Mesh Tidak Terstruktur Tiga Dimensi: Bagian 3. Volume Meshes // Metode Komputer Dalam Mekanika Dan Teknik Terapan, Elsevier, Vol 134, hal. 285-310, 1996.
26. A.Liu, B.Joe. Tentang Bentuk Tetrahedra Dari Bisection // Matematika Komputasi, vol. 63, No. 207, 141-154, 1994.
27. SH. lihat Diskritisasi Volume menjadi Tetrahedra-I. Verifikasi dan Orientasi Permukaan Batas // Komputer dan Struktur, Pergamon Press, Vol. 39, no.5, hal. 493-500, 1991.
28. SH. lihat Diskritisasi Volume menjadi Tetrahedra - II. Triangulasi 3D dengan Memajukan Pendekatan Depan // Komputer dan Struktur, Pergamon, Jil. 39, no.5, hal. 501-511, 1991.
29. R. Lohner. Pembangkitan Kisi-Kisi Tidak Terstruktur Tiga Dimensi Dengan Metode Muka Maju // Prosiding Pertemuan Ilmu Kedirgantaraan AIAA ke-26, Reno, Nevada, 1988.
30. SJ Owen. Survei Teknologi Pembuatan Mesh Tidak Terstruktur // Prosiding Meja Bundar Meshing Internasional ke-7, hal. 239-269, Dearborn, MI, 1998.
31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. Perbandingan Ukuran Kualitas Tetrahedron // Elemen Hingga dalam Analisis dan Desain, Elsevier, tidak. 15, hal. 255-261, 1993.
32. S. Pirzadeh. Pembuatan Kisi-kisi Viscous Tidak Terstruktur dengan Metode Advancing-Layers // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.
33. V.T. raja. Optimalitas Triangulasi Delaunay di // Prok. Gejala ACM ke-7 Komp. geometri, hal. 357-363, 1991.
34. A. Rassinux. Pembuatan dan Optimalisasi Tetrahedral Meshes dengan Memajukan Teknik Depan // Jurnal Internasional untuk Metode Numerik dalam Rekayasa, Wiley, Vol. 41, hal. 651-674, 1998.
35. S.Rebay. Pembuatan Mesh Tidak Terstruktur yang Efisien dengan Triangulasi Delaunay dan Algoritma Bowyer-Watson // Jurnal Fisika Komputasi, vol. 106, hal. 125-138, 1993.
36. M.-C. Rivara. Selective Refinement/Derefinement Algorithms Untuk Urutan Triangulasi Bersarang // Jurnal Internasional untuk Metode Numerik dalam Rekayasa, No. 28, hal. 2889-2906, 1998.
37. M.-C. Rivara, C. Levin. Algoritma Penyempurnaan 3D yang Cocok Untuk Teknik Adaptif Dan Multigrid // Komunikasi dalam Metode Numerik Terapan, No. 8, hal. 281-290, 1998.
38. J. Ruppert. Algoritme penyempurnaan Delaunay untuk pembuatan mesh 2 dimensi berkualitas // Jurnal Algoritma, No. 18, hal. 548-585, 1995.
39. NONA. Gembala, M.K. Georges. Pembuatan Mesh Tiga Dimensi dengan Teknik Oktre Hingga // Jurnal Internasional untuk Metode Numerik dalam Rekayasa, vol. 32, hal. 709-749, 1991.
40. NONA. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Pembuatan octree mesh terbatas untuk Analisis Aliran 3D adaptif otomatis // Pembangkitan grid numerik dalam mekanika fluida komputasi Miami, 1988
41. K.Shimada, D.C. Gossard. Bubble Mesh: Meshing Segitiga Otomatis dari Geometri Non-manifold dengan Sphere Packing // prosiding dari Simposium ke-3 tentang Pemodelan dan Aplikasi Padat , hal. 409-419, 1995.
42. K. Shimada, A. Yamada, T. Itoh. Anisotropic Triangular Meshing dari Permukaan Parametrik melalui Pengepakan Gelembung Ellipsoidal // Prosiding Meja Bundar Meshing Internasional ke-6, hal. 375-390, 1997.
43. D.F. Watson. Menghitung Delaunay Tessellation dengan Aplikasi ke Politop Voronoi // Jurnal Komputer, Jil. 24(2), hal. 167-172, 1981.
44. MA Yerry, M.S. Gembala. Pembuatan Mesh Tiga Dimensi dengan Teknik Oktre yang Dimodifikasi // Jurnal Internasional untuk Metode Numerik dalam Rekayasa, Jil. 20, hal. 1965-1990, 1984.
45. Galanin M.P., Shcheglov I.A. Pengembangan dan implementasi algoritma untuk triangulasi tiga dimensi dari wilayah spasial yang kompleks: metode langsung. pracetak IPM im. M.V. Keldysh RAN, 2006, dalam pers. poin, yaitu Simpul Steiner - simpul tambahan yang tidak termasuk dalam set asli
Tampaknya kondisi 2 mengikuti dari kondisi 3, tetapi kenyataannya tidak. Misalnya, tetrahedron yang ada mungkin seluruhnya dalamtetrahedron yang diuji.
