Rumah Rongga mulut Metode bola kosong Delaunay. Konstruksi dalam kasus umum

Rongga mulut

Metode bola kosong Delaunay. Konstruksi dalam kasus umum

20 Agustus 2012 pukul 22:41

Optimalisasi algoritma pengecekan kondisi Delaunay melalui persamaan sirkumlingan dan penerapannya

Saya akan memberi tahu Anda rahasia cara cepat memeriksa kondisi Delaunay untuk dua segitiga.
Sebenarnya, optimasi itu sendiri dijelaskan sedikit lebih rendah (lihat "Optimasi algoritma untuk memeriksa kondisi Delaunay melalui persamaan lingkaran"), tetapi saya akan memberi tahu Anda semuanya secara berurutan.

Dalam kasus saya, triangulasi digunakan dalam penelusuran gambar untuk membagi bidang menjadi sektor primitif (segitiga). Seperti diketahui, ini juga dibagi menjadi beberapa tahap: penyesuaian, identifikasi batas, berjalan mengelilingi batas, menyapu kontur. Itu ada di bagian paling atas pandangan umum. Saya benar-benar ingin berhenti, saya pikir tahap yang sulit: menyapu pesawat.

Di pintu masuk

Setelah mendeteksi dan melintasi batas, saya mendapatkan banyak loop luar pada output. Setiap kontur yang menyentuh memiliki warna yang berbeda. Setiap sirkuit tersebut juga berisi sejumlah sirkuit internal yang diketahui.
Jadi, dari sudut pandang “menyapu bidang”, jika kita mempertimbangkan kontur luar secara terpisah, kita memiliki sekumpulan titik, yang masing-masing memiliki satu tetangga di kanan dan kiri. Itu. semua titik tertutup dalam satu rantai, tidak ada satu titik pun yang “menggantung”, dan setiap rantai berisi setidaknya 3 titik (Gambar 1).

Gambar 1

Apa yang perlu dilakukan

Anda perlu menutupi gambar itu dengan segitiga.

Mencari

Setelah membaca buku tersebut, saya tidak menemukan satu pun (setidaknya satu) metode membangun triangulasi Delaunay yang setidaknya cocok untuk kasus saya. Saya tidak mencari buku lain. Dan ini sudah cukup, itu membuat pikiranku tertata rapi. Hasilnya, dia menemukan “sepeda” miliknya sendiri.

Algoritma

1) Mari kita asumsikan, sebagai permulaan, hanya ada satu barisan pada gambar yang ditinjau. Kemudian semuanya bermuara pada pengambilan segitiga secara berurutan. Kami mengambil titik mana pun dan mencoba membuat segitiga dengan titik-titik yang berdekatan. Jika tidak mungkin membuat segitiga (garis yang menghubungkan kedua titik ini berpotongan dengan yang sudah dibangun atau garis melewati zona eksklusi (Gambar 2), kita pindah ke titik berikutnya, katakanlah ke kanan. Kapan segitiga berikutnya ditemukan, kami menambahkannya ke daftar (Gambar 3), dan menghapus titik asal pembuatannya (Gambar 4).

Gambar 2

Gambar 3

Gambar 4

Satu hal lagi: saat menyimpan segitiga berikutnya, perlu untuk mencatat simpul-simpul dalam traversal 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 barisan, 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 internal lainnya. Dari satu eksternal dan satu internal kita akan membuat dua sirkuit tunggal. Untuk melakukan ini, Anda perlu menemukan dua “port” dari satu sirkuit ke sirkuit lainnya. Syarat untuk “pelabuhan”: tidak boleh berpotongan satu sama lain (bahkan ujungnya tidak boleh bersentuhan), dan tidak boleh berpotongan dengan garis kontur (Gambar 5).

Gambar 5

Gambar 6
4) Selanjutnya, Anda harus memasukkan satu per satu semua barisan internal ke dalam barisan yang sudah terbentuk, terpisah satu sama lain (poin 3). Anda perlu menggabungkannya dengan yang berisi yang baru. Menurut definisinya, tidak ada rangkaian internal yang bersentuhan atau bersinggungan dengan yang lain (baik yang eksternal maupun semua kemungkinan internal), sehingga semuanya akan berjalan lancar.
Setelah menemukan port (Gambar 6), mudah untuk membuat urutan baru dan melewatinya menggunakan poin 1 dan 2 dari algoritma saat ini (Gambar 7).

Gambar 7

5) Setelah tahap ke-4 kita memiliki daftar segitiga (Gambar 8). Tugasnya seolah-olah sudah selesai, namun yang tersisa hanyalah mempercantik gambarnya: periksa apakah kondisi Delaunay terpenuhi (Gambar 9).

Angka 8

Gambar 9

6) Kedepannya saya akan bercerita tentang poin keenam. Ini terdiri dari menelusuri daftar segitiga yang diperoleh secara berurutan menggunakan langkah No. 5. Pertama, kita tandai semua segitiga sebagai “kotor”. Di setiap siklus kami memeriksa kondisi Delaunay untuk setiap segitiga. Jika kondisi tidak terpenuhi, maka kita membangun kembali dan menandai tetangga dan segitiga saat ini sebagai “kotor”. Jika syaratnya terpenuhi baru kita tandai bersih. Dalam implementasi algoritma saya, setiap segitiga memiliki tautan ke tetangganya. Dalam hal ini, poin 6 bekerja paling cepat.

Lebih lanjut tentang tahap kelima

Sekarang, sejauh yang saya tahu, ada dua cara yang mungkin tentukan apakah segitiga memenuhi syarat Delaunay atau tidak: 1) Periksa jumlah sudut yang berhadapan. Harus kurang dari 180. 2) Hitung pusat lingkaran yang dibatasi dan hitung jarak ke titik ke-4. Semua orang mengetahui bahwa kondisi Delaunay terpenuhi jika titik tersebut berada di luar lingkaran yang dibatasi.

Daya komputasi #1: 10 kali/bagi dan 13 tambah/kurang.
Daya komputasi #2: 29 kali/bagi dan 24 tambah/kurang.

Dari sudut pandang daya komputasi, yang dihitung misalnya di buku, opsi No. 1 lebih menguntungkan. Saya akan menerapkannya, jika tidak... (Gambar 10). Ternyata setelah produksi metode ini ke “ban berjalan”, hasilnya adalah ketidakpastian. Ini adalah pilihan bila sudut A sendiri lebih dari 180 derajat. Hal ini dianggap dalam buku sebagai salah satu metode pribadi individu. Dan dengan ini, semua keanggunan, transparansi, dan kinerjanya lenyap. Dan ternyata cara no. 2 juga bisa dioptimalkan secara signifikan.

Gambar 10

Optimalisasi algoritma pengecekan kondisi Delaunay melalui persamaan lingkaran luar

Berikutnya adalah matematika murni.

Jadi kita punya:
Pengecekan kondisi titik M(X, Y) dengan persamaan lingkaran yang melalui titik A(x1, y1), B(x2, y2), C(x3, y3) dapat dituliskan sebagai:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ tanda tangan a ≥ 0

Detailnya dapat ditemukan di buku yang luar biasa ini. (Tidak, saya bukan penulisnya)
Jadi tanda a adalah tanda arah traversal, dari awal saya buat segitiganya searah jarum jam, jadi bisa dihilangkan (sama dengan satu).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Gambar 11

Sederhana 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 menunggu kritik.

Bibliografi

1. Skvortsov A.V. Triangulasi Delaunay dan penerapannya. – Tomsk: Rumah penerbitan Tom. Universitas, 2002. – 128 hal. ISBN 5-7511-1501-5

Model GRID adalah model sel biasa.

Biarkan sistem koordinat diperkenalkan
Dan Dan
. Kumpulan pengguna
dan langkah pengambilan sampel
.

- koordinat fisik suatu titik.

Kami menghitung
Dan
,
- jaringan kecil.

- nilai terkuantisasi. Nyata:

- parameter algoritma – jumlah poin, - berat. Semakin dekat titiknya, semakin besar bobotnya.

- derajat jarak (1 atau 2).

Koefisien normalisasi:

Bagaimana mendekati 1, semakin banyak poin dengan bobot lebih tinggi yang diperhitungkan.

Ini adalah metode IDW - ini panjang, untuk setiap t perlu mencari tetangga. Himpunan tetangga dapat ditemukan secara efisien - terdekat. Setiap titik menghasilkan “pasak” dengan ketinggian tertentu. Banyak hal bergantung pada ketidakteraturan dalam menetapkan maksudnya;
atau
itu. dibagi menjadi beberapa sektor dan membangun titik di sekitarnya.

Keuntungan– kesederhanaan

Kekurangan:

------Tiket 14. Model timah. Algoritma triangulasi Delaunay ------

1) Triangulasi (timah).

Triangulasi– konstruksi suatu fungsi dalam bentuk himpunan fungsi linier sepotong-sepotong

Triangulasi– interpolasi dalam wilayah cembung.

Triangulasi– graf planar yang semua sisi dalamnya berbentuk segitiga; cara merepresentasikan ruang dalam bentuk segitiga yang saling berdekatan tanpa tumpang tindih. Triangulasi dibangun berdasarkan sekumpulan poin dalam beberapa cara.

Diperlukan suatu algoritma untuk membangun triangulasi yang optimal.

Sebuah pesawat melewati 3 titik.

1) Temukan segitiga itu
;

2)
- buatlah persamaan bidang.

Untuk memeriksa apakah titik-titik tersebut berada di dalam segitiga atau tidak, Anda perlu mensubstitusikan nilainya ke dalam persamaan garis – rusuk segitiga. Jika ketiga persamaan > 0, maka di dalam.

Struktur presentasi:

Setiap triangulasi berisi jumlah segitiga yang sama.

, Di mana – jumlah poin internal,
- jumlah poin.

Triangulasi serakah.

Kami menghubungkan semua titik dengan tepi, memilih minimum, dan menambahkannya ke triangulasi. Selanjutnya kita ambil minimum berikutnya yang tidak berpotongan dengan minimum sebelumnya, dan seterusnya. Hasilnya adalah triangulasi serakah.

Triangulasi Delaunay.

Bagian dalam lingkaran yang dibatasi pada suatu segitiga tidak termasuk titik-titik segitiga lainnya. Itu dibangun dengan satu-satunya cara.

Flip adalah perpindahan tepian. Hal ini memungkinkan Anda beralih dari triangulasi konvensional ke triangulasi Delaunay. Untuk memeriksa apakah suatu titik termasuk dalam lingkaran: gantikan if< R, то внутри.

Kondisi Delaunay.

Persamaan lingkaran yang melalui tiga titik:

Jika kurang dari nol, maka eksternal, jika tidak, internal.

– Kondisi Delaunay.

Algoritma untuk membangun triangulasi Delaunay:

1) Menambahkan titik-titik yang sedang diselidiki– algoritma iteratif sederhana:

Ada satu set
tambahkan ke segitiga, konstruksi dilakukan
pemisahan segitiga
pembangunan kembali. Pada tahap nol, kita tambahkan 3-4 titik fiktif, yang jelas-jelas menutupi amplop kita, semua titik di dalamnya. Kemudian kita lempar titiknya, lihat segitiga mana yang terkena, bagi menjadi 3, untuk setiap segitiga kita periksa kondisi Delaunay dan lakukan perpindahan tepi secara terbalik. Jumlah rata-rata pergantian jalur adalah tiga.

Kompleksitas teoritis

2) Metode akselerasi. Berdasarkan poin-poin yang bergantung secara statistik. Segitiga benih adalah segitiga tempat jatuhnya titik sebelumnya. Kemudian kita menghubungkan dua titik - yang sebelumnya dan yang baru.

Kami berpindah dari poin pertama ke poin lainnya.

20 Agustus 2012 pukul 22:41

Optimalisasi algoritma pengecekan kondisi Delaunay melalui persamaan sirkumlingan dan penerapannya

Pengolahan citra ,
Pemrograman

Dalam kasus saya, triangulasi digunakan dalam penelusuran gambar untuk membagi bidang menjadi sektor primitif (segitiga). Seperti diketahui, ini juga dibagi menjadi beberapa tahap: penyesuaian, identifikasi batas, berjalan mengelilingi batas, menyapu kontur. Ini adalah istilah yang paling umum. Saya pikir, saya ingin berhenti pada tahap yang paling sulit: menyapu pesawat.

Di pintu masuk

Setelah mendeteksi dan melintasi batas, saya mendapatkan banyak loop luar pada output. Setiap garis yang menyentuh memiliki warna yang berbeda. Setiap sirkuit tersebut juga berisi sejumlah sirkuit internal yang diketahui.
Jadi, dari sudut pandang “menyapu bidang”, jika kita mempertimbangkan kontur luar secara terpisah, kita memiliki sekumpulan titik, yang masing-masing memiliki satu tetangga di kanan dan kiri. Itu. semua titik tertutup dalam satu rantai, tidak ada satu titik pun yang “menggantung”, dan setiap rantai berisi setidaknya 3 titik (Gambar 1).

Gambar 1

Apa yang perlu dilakukan

Anda perlu menutupi gambar itu dengan segitiga.

Mencari

Algoritma

Gambar 2

Gambar 3

Gambar 4

2) Ulangi langkah 1 sampai kita menyapu seluruh bidang.

Lebih lanjut tentang tahap kelima

Sejauh yang saya tahu, ada dua cara yang mungkin untuk menentukan apakah segitiga memenuhi kondisi Delaunay atau tidak: 1) Periksa jumlah sudut yang berhadapan. Harus kurang dari 180. 2) Hitung pusat lingkaran yang dibatasi dan hitung jarak ke titik ke-4. Semua orang mengetahui bahwa kondisi Delaunay terpenuhi jika titik tersebut berada di luar lingkaran yang dibatasi.

Daya komputasi #1: 10 kali/bagi dan 13 tambah/kurang.
Daya komputasi #2: 29 kali/bagi dan 24 tambah/kurang.

Dari sudut pandang daya komputasi, yang dihitung misalnya di buku, opsi No. 1 lebih menguntungkan. Saya akan menerapkannya, jika tidak... (Gambar 10). Ternyata, setelah menerapkan metode ini pada “konveyor”, timbul ketidakpastian. Ini adalah pilihan bila sudut A sendiri lebih dari 180 derajat. Hal ini dianggap dalam buku sebagai salah satu metode pribadi individu. Dan dengan ini, semua keanggunan, transparansi, dan kinerjanya lenyap. Dan belakangan ternyata cara no. 2 bisa dioptimasi dengan sangat signifikan.

Gambar 10

Optimalisasi algoritma pengecekan kondisi Delaunay melalui persamaan lingkaran luar

Berikutnya adalah matematika murni.

Jadi kita punya:
Pengecekan kondisi titik M(X, Y) dengan persamaan lingkaran yang melalui titik A(x1, y1), B(x2, y2), C(x3, y3) dapat dituliskan sebagai:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ tanda tangan a ≥ 0

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D>=0

Gambar 11

Sederhana 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 menunggu kritik.

Bibliografi

1. Skvortsov A.V. Triangulasi Delaunay dan penerapannya. – Tomsk: Rumah penerbitan Tom. Universitas, 2002. – 128 hal. ISBN 5-7511-1501-5

Definisi dan properti dasar

Triangulasi adalah graf planar yang semua daerah dalamnya berbentuk segitiga.

Properti:

· Triangulasi Delaunay berhubungan satu-satu dengan diagram Voronoi untuk himpunan titik yang sama.

· Konsekuensinya: jika tidak ada empat titik yang terletak pada lingkaran yang sama, triangulasi Delaunay bersifat unik.

· Triangulasi Delaunay memaksimalkan sudut minimum di antara semua sudut dari semua segitiga yang dibangun, sehingga menghindari segitiga “tipis”.

· Triangulasi Delaunay memaksimalkan jumlah jari-jari bola yang tertulis.

· Triangulasi Delaunay meminimalkan fungsi Dirichlet diskrit.

· Triangulasi Delaunay meminimalkan radius maksimum dari lingkungan sekitar minimum.

· Triangulasi Delaunay pada bidang mempunyai jumlah minimum jari-jari lingkaran yang mengelilingi segitiga di antara semua kemungkinan triangulasi.

Gambar 1. Triangulasi.

Triangulasi cembung adalah triangulasi yang poligon minimum yang melingkupi semua segitiga adalah cembung. Triangulasi yang tidak cembung disebut noncembung.

Masalah membangun triangulasi dari himpunan titik-titik dua dimensi tertentu adalah masalah menghubungkan titik-titik tertentu dengan segmen-segmen yang tidak berpotongan sehingga terbentuklah triangulasi.

Suatu triangulasi dikatakan memenuhi kondisi Delaunay jika tidak ada titik triangulasi yang berada di dalam lingkaran yang dibatasi di sekitar segitiga yang dibangun.

Suatu triangulasi disebut triangulasi Delaunay jika triangulasi tersebut cembung dan memenuhi kondisi Delaunay.

Gambar 2. Triangulasi Delaunay.

Metode bola kosong Delaunay. Konstruksi dalam kasus umum

Mari kita gunakan sebuah bola kosong, yang akan kita gerakkan, ubah ukurannya sehingga dapat menyentuh titik-titik sistem (A), tetapi selalu tetap kosong.

Jadi, mari kita tempatkan bola Delaunay yang kosong dalam sistem poin (A). Hal ini selalu memungkinkan jika Anda memilih bola yang cukup kecil. Mari kita mulai meningkatkan radiusnya, membiarkan bagian tengah bola tetap di tempatnya. Pada suatu titik permukaan bola akan bertemu dengan suatu titik i dari sistem (A). Ini pasti akan terjadi, karena tidak ada kekosongan yang sangat besar di sistem kita. Kita akan terus memperbesar jari-jari bola kosong tersebut sehingga titik i tetap berada di permukaannya. Untuk melakukan ini, Anda harus memindahkan bagian tengah bola dari titik i. Cepat atau lambat bola akan mencapai titik lain dalam sistem (A) dengan permukaannya.

Gambar.3

Delaunay simpleks mengisi ruang tanpa celah atau tumpang tindih.

Bidang simpleks apa pun yang dideskripsikan tidak memuat titik-titik lain dari sistem di dalamnya.

Biarlah ini menjadi poin j. Mari terus tingkatkan jari-jari bola kita, pertahankan kedua titik di permukaannya. Ketika bola bertambah, ia akan mencapai titik ketiga dari sistem, titik k. Dalam kasus dua dimensi, “lingkaran kosong” kita akan diperbaiki pada saat ini, yaitu. Menjadi tidak mungkin untuk meningkatkan radiusnya lebih jauh sambil menjaga lingkaran tetap kosong. Pada saat yang sama, kami mengidentifikasi konfigurasi dasar dua dimensi dari tiga titik (i, j, k), yang mendefinisikan segitiga tertentu, yang kekhasannya adalah tidak ada titik lain dari sistem (A) di dalam lingkaran luarnya. Dalam ruang tiga dimensi, sebuah bola tidak dibatasi oleh tiga titik. Mari kita terus tingkatkan radiusnya, pertahankan ketiga titik yang ada di permukaannya. Hal ini dapat dilakukan sampai permukaan bola bertemu dengan titik keempat l dari sistem. Setelah ini, pergerakan dan pertumbuhan bola kosong menjadi tidak mungkin. Empat titik yang ditemukan (i,j,k,l) mendefinisikan simpul-simpul tetrahedron, yang dicirikan oleh fakta bahwa di dalam bola yang dibatasi tidak ada titik-titik lain dari sistem (A). Tetrahedron seperti itu disebut Delaunay simplex.

Dalam matematika, simpleks adalah bangun ruang paling sederhana dengan dimensi tertentu: tetrahedron - dalam ruang tiga dimensi; segitiga - dalam dua dimensi. Tiga (empat) titik sembarang dari sistem yang tidak terletak pada bidang yang sama selalu mendefinisikan suatu simpleks tertentu. Namun, ini akan menjadi simpleks Delaunay hanya jika bola yang dideskripsikannya kosong. Dengan kata lain, penyederhanaan Delaunay ditentukan oleh pilihan khusus dari titik kembar tiga (empat kali lipat) dalam sistem (A).

Kita telah membuat satu simpleks Delaunay, namun dengan menempatkan bola kosong di tempat yang berbeda dan mengulangi prosedur yang sama, maka yang lain dapat ditentukan. Dinyatakan bahwa himpunan semua penyederhanaan Delaunay dari sistem (A) mengisi ruang tanpa tumpang tindih dan celah, yaitu. menerapkan pembagian ruang, tapi kali ini menjadi tetrahedron. Partisi ini disebut Ubin Delaunay(Gbr. 3).

Penerapan triangulasi Delaunay

Triangulasi Delaunay sering digunakan dalam ruang Euclidean. Pohon rentang minimum Euclidean dijamin terletak pada triangulasi Delaunay, sehingga beberapa algoritma menggunakan triangulasi. Juga, melalui triangulasi Delaunay, masalah penjual keliling Euclidean kira-kira terpecahkan.

Dalam interpolasi 2D, triangulasi Delaunay membagi bidang menjadi segitiga setebal mungkin, menghindari sudut yang terlalu lancip dan terlalu tumpul. Dengan menggunakan segitiga ini, Anda dapat membuat, misalnya, interpolasi bilinear.

Masalah lain yang sering ditemui dalam geoinformatika adalah konstruksi paparan lereng. Di sini perlu ditentukan arah dominan lereng berdasarkan arah mata angin dan membagi permukaan menjadi daerah-daerah yang didominasi arah tertentu. Karena penentuan eksposur tidak masuk akal untuk area permukaan horizontal, area yang horizontal atau sedikit miring dialokasikan ke wilayah terpisah, misalnya<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Gambar.4.

Masalah penghitungan eksposur lereng biasanya digunakan untuk menganalisis iluminasi bumi. Dalam hal ini, seringkali ada kebutuhan untuk memperhitungkan posisi Matahari saat ini, yaitu. paparan dihitung sebagai arah antara garis normal ke segitiga dan arah ke Matahari.

Dengan demikian, setiap segitiga triangulasi dapat diklasifikasikan menurut prinsip kepemilikan suatu wilayah tertentu. Setelah ini, Anda hanya perlu memanggil algoritma pemilihan wilayah.

Triangulasi adalah perkiraan permukaan suatu benda yang dimodelkan dengan pelat-pelat segitiga yang berjarak tidak melebihi nilai tertentu yang ditentukan 6. Semua pelat segitiga harus disambung. Puncaknya terletak di permukaan. Seperangkat pelat segitiga lebih mudah dikerjakan dibandingkan permukaan umum. Kami akan menyebut pelat segitiga sebagai segitiga. Untuk sebuah segitiga, jarak ke suatu titik tertentu atau titik perpotongan dengan garis tertentu dalam ruang dihitung dengan cepat. Triangulasi wajah dilakukan untuk persepsi visual model geometris, sehingga sisi-sisi segitiga dipilih agar mata tidak dapat melihat kekusutannya.

Saat menampilkan objek geometris dalam bentuk segitiga pada bidang parametrik permukaan, triangulasi spasial permukaan benda harus dibangun dengan menghitung larik titik-titik dalam ruang dan larik normal ke muka benda pada titik-titik tersebut menggunakan larik. titik dua dimensi. Untuk menampilkan benda dengan cepat, permukaannya didekati dengan pelat segitiga yang dibangun di atas Titik normal diperlukan untuk menentukan perilaku sinar cahaya yang berinteraksi dengan permukaan benda. Gambar nada pada bab sebelumnya dan bab ini dibuat dengan menggunakan triangulasi.

Sebagai hasil dari triangulasi permukaan, kita ingin memiliki larik titik dua dimensi pada bidang parametrik dan larik kembar tiga bilangan bulat, yang merupakan jumlah titik pada larik yang disebutkan pertama. Jadi, setiap segitiga akan diwakili oleh tiga nomor simpulnya dalam larik parameter. Untuk setiap titik dua dimensi dari domain parametrik, titik spasial pada permukaan dan permukaan normal di dalamnya dapat dihitung. Titik spasial dan normal dapat disimpan dalam array yang mirip dengan array titik 2D.

Mari kita lihat beberapa metode triangulasi. Untuk permukaan datar, terdapat metode triangulasi yang hemat biaya di mana segitiga dibuat pada titik batas permukaan dan tidak perlu mencari titik di dalam daerah parametrik.

Triangulasi Delaunay.

Mari kita pertimbangkan beberapa area di pesawat. Suatu daerah disebut cembung jika pada saat bergerak sepanjang batasnya harus berbelok hanya ke satu arah (ke kiri saja atau ke kanan saja). Algoritma Delaunay dapat digunakan untuk melakukan triangulasi daerah planar cembung. Kami tidak dapat langsung menerapkan algoritme ini untuk melakukan triangulasi permukaan bentuk bebas, namun kami akan menggunakan metodenya untuk membuat segitiga.

Beras. 9.7.1. Daerah cembung dengan titik-titik tertentu di dalamnya

Misalkan diberikan suatu daerah dua dimensi cembung yang dibatasi oleh garis putus-putus tertutup dan sekumpulan titik di dalam daerah tersebut (Gbr. 9.7.1).

Area tertentu harus dibagi menjadi segitiga-segitiga, yang simpul-simpulnya adalah titik-titik tertentu di dalam luas tersebut dan simpul-simpul dari garis putus-putus yang membatasinya. Segitiga tidak boleh saling tumpang tindih, dan sisi-sisinya hanya boleh berpotongan di titik sudutnya.

Beberapa rangkaian segitiga yang berbeda dapat dibuat untuk mengisi area tertentu. Dalam semua kasus, jumlah segitiga sama dengan , dengan K adalah jumlah simpul dari polyline pembatas, I adalah jumlah titik tertentu di dalam luas tersebut.

Beras. 9.7.2. Memilih poin ketiga dari algoritma Delaunay

Triangulasi suatu daerah akan menjadi triangulasi Delaunay jika tidak ada titik sudut dari segitiga lain di dalam lingkaran yang mengelilingi setiap segitiga. Triangulasi Delaunay membangun segitiga sedekat mungkin dengan sudut yang sama (tidak memungkinkan konstruksi segitiga yang memanjang secara tidak wajar).

Itu bisa disebut seimbang. Triangulasi Delaunay akan menjadi unik jika tidak ada empat simpul yang terletak pada lingkaran yang sama.

Mari kita perhatikan triangulasi Delaunay. Kita akan menyebut simpul-simpul dari polyline yang membatasi daerah tersebut dan titik-titik tertentu di dalam daerah tersebut sebagai simpul-simpul triangulasi. Kita akan menyebut sisi-sisi segitiga sebagai rusuk. Di antara tepinya, kami memilih segmen dari polyline pembatas, yang akan kami sebut tepi batas. Mari kita arahkan semua sisi batas sehingga daerah cembung terletak di sebelah kiri setiap sisi. Misalkan kita perlu membuat sebuah segitiga, yang sisinya merupakan tepi batas AB, ditunjukkan pada Gambar. 9.7.2.

Melalui titik A, B dan setiap titik yang tidak terletak pada garis yang sama dengannya, dapat dibuat sebuah lingkaran. Sebagai titik sudut ketiga dari segitiga, kita memilih titik sudut V, lingkaran yang bersesuaian tidak memuat titik-titik lain pada sisi yang sama relatif terhadap ruas AB di mana titik V terletak ditemukan. Kami akan menyebutnya yang terdekat. Pusat lingkaran yang melalui titik A, B, dan V terletak pada perpotongan garis tegak lurus titik tengah segmen AB, BV, dan VA. Letak pusat lingkaran akan dicirikan oleh parameter t ruas MN, tegak lurus tepi AB, sama panjang dan melalui titik tengah tepi AB.

Beras. 9.7.3. Proses triangulasi Delaunay

Untuk semua simpul yang terletak di sebelah kiri ruas AB, simpul terdekat mempunyai parameter terkecil t. Lingkaran yang bersesuaian dengan simpul terdekat tidak memuat simpul lain di sebelah kiri ruas AB. Misalkan simpul A, B dan V masing-masing digambarkan oleh vektor jari-jari dua dimensi. Vektor jari-jari titik tengah ruas AB dan BV akan sama

Nilai parameter t garis yang sesuai dengan posisi pusat lingkaran yang melalui titik A, B dan V di atasnya adalah sama dengan

Untuk simpul yang paling dekat dengan kiri ruas AB, parameter t mempunyai nilai minimum.

Mari kita arahkan semua tepi batas sehingga area yang akan ditriangulasi terletak di sebelah kiri masing-masing tepi tersebut. Kami mulai membuat segitiga dari tepi batas mana pun. Mari kita cari titik terdekatnya, yang lingkarannya tidak memuat simpul lain. Misalkan titik sudut V terdekat ditemukan pada tepi batas AB. Kemudian kita buat segitiga ABV dan pindahkan tepi AB ke kategori tidak aktif. Kami akan memanggil tepi dan simpul tidak aktif yang tidak berpartisipasi dalam algoritma triangulasi. Jika tidak ada tepi BV di antara tepi batas, maka kita buat tepi batas baru pada segmen VB. Jika di antara tepi batas terdapat tepi BV, maka tepi tersebut dan simpul B kita pindahkan ke kategori tidak aktif. Jika tidak ada tepi VA di antara tepi batas tersebut, maka kita akan membuat tepi batas baru pada ruas AV. Jika di antara tepi batas terdapat tepi VA, maka kita pindahkan dan simpul A ke dalam kategori tidak aktif. Proses triangulasi ditunjukkan pada Gambar. 9.7.3.

Beras. 9.7.4. triangulasi Delaunay

Kami menyelesaikan triangulasi ketika semua simpul dan tepi menjadi tidak aktif. Hasil triangulasi suatu luas tertentu ditunjukkan pada Gambar. 9.7.4.

Triangulasi dengan metode koreksi.

Mari kita pertimbangkan triangulasi permukaan tertentu dengan domain persegi panjang untuk menentukan parameter. Kami membagi domain untuk menentukan parameter permukaan menjadi sel persegi panjang dengan garis dua dimensi. Mari kita ambil jarak parametrik antara garis yang berdekatan sesuai dengan rumus (9.4.7) menjadi sama

Mari kita ambil jarak parametrik antara garis yang berdekatan sesuai dengan rumus (9.4.8) menjadi sama

Dengan membuat diagonal di semua sel persegi panjang, kita memperoleh triangulasi permukaan (kita memperoleh sekumpulan segitiga yang memenuhi persyaratan). Pada Gambar. 9.7.5 menunjukkan triangulasi permukaan revolusi menggunakan metode yang dijelaskan.

Mari kita perhatikan triangulasi suatu permukaan dengan batas yang berubah-ubah. Kami akan membangun metode triangulasi berdasarkan koreksi kontur batas triangulasi permukaan yang dijelaskan di atas dengan luas persegi panjang untuk menentukan parameter.

Beras. 9.7.5. Triangulasi permukaan dengan domain persegi panjang untuk menentukan parameter

Biarkan batas permukaan dalam domain definisi parameter dijelaskan oleh beberapa kontur dua dimensi yang tidak berpotongan (2.12.7). Salah satu kontur bersifat eksternal dan berisi kontur lainnya. Untuk arah positif setiap kontur kita ambil arah yang bila bergerak sepanjang, luas definisi permukaan selalu berada di sebelah kiri kontur, jika dilihat ke arah normal permukaan. Mari kita buat poligon dalam arah positif dari kontur batas luas definisi permukaan. Untuk membuat poligon batas, Anda perlu menelusuri kontur batas permukaan dengan beberapa langkah variabel dan mengisi larik titik dua dimensi, yang koordinatnya merupakan parameter permukaan. Kita akan membangun poligon dari titik-titik pada bidang parametrik, tetapi langkah perpindahan dari satu titik ke titik lain akan ditentukan dari geometri spasial, yaitu dari kondisi defleksi busur kurva antara titik-titik yang berdekatan tidak lebih dari suatu yang diberikan. nilai. Kami menghitung langkah parametrik untuk membuat poligon untuk kurva kontur batas permukaan menggunakan rumus (9.4.4).

Setiap poligon terdiri dari sekumpulan titik dua dimensi yang terurut. Setiap bagian poligon dapat dianggap sebagai segmen garis lurus dua dimensi yang dibangun di atas dua titik yang berdekatan. Kita akan menggunakan area tersebut sebagai tepi batas, dan titik-titik poligon yang menjadi dasar tepi tersebut akan digunakan sebagai simpul triangulasi. Karena luas untuk menentukan parameter permukaan terletak di sebelah kiri poligon batas, ketika membuat segitiga untuk setiap tepi triangulasi batas, Anda harus mencari titik sudut ketiga segitiga di sebelah kiri tepi.

Mari kita tentukan node mana yang terletak di dalam poligon batas, dan mana yang terletak di perbatasan atau di luar area definisi permukaan. Dengan menggunakan informasi ini, kami mengurutkan sel kotak persegi panjang menjadi dua kelompok. Kelompok pertama mencakup sel-sel yang seluruhnya terletak di dalam area di mana parameter permukaan ditentukan (sel tidak boleh menyentuh poligon batas). Kelompok kedua mencakup sel-sel yang tersisa (terletak di luar area definisi permukaan atau berpotongan dengan poligon batas).

Beras. 9.7.6. Triangulasi permukaan yang belum selesai

Di dalam setiap sel kelompok pertama, dengan menggunakan diagonal, kita akan membuat dua segitiga. Jadi kita mendapatkan triangulasi yang belum selesai. Contoh pembuatan segitiga dalam sel kelompok pertama untuk permukaan revolusi yang dibatasi oleh kontur ditunjukkan pada Gambar. 9.7.6.

Kami akan membuat tepi batas pada sisi yang tidak berpotongan dari sel kelompok kedua dan mengarahkannya sehingga sel yang bersesuaian berada di sebelah kiri tepi. Di sekitar sel-sel kelompok pertama, kita akan membuat garis putus-putus yang tertutup (mungkin beberapa garis tertutup) sehingga ketika bergerak sepanjang itu, bagian dari area yang tidak terbagi menjadi segitiga terletak di sebelah kiri, jika dilihat ke arah permukaan normal. . Kita juga akan menggunakan bagian lurus dari garis putus-putus ini sebagai tepi pembatas. Kami akan menganggap semua sisi sama. Untuk menyelesaikan triangulasi, kita perlu membuat segitiga di antara tepi batasnya. Untuk setiap sisi kita akan mencari titik sudut yang terletak di sebelah kirinya dan dapat digunakan untuk membuat segitiga. Kami akan mencari sebuah simpul hanya di antara simpul-simpul yang terletak di sel yang sama dengan tepinya. Untuk memilih sebuah titik, kami menggunakan metode Delaunay yang dijelaskan di atas dan diilustrasikan pada Gambar. 9.7.2. Jika titik sudut seperti itu ditemukan, maka Anda harus memeriksa apakah dua sisi baru segitiga tersebut berpotongan dengan tepi batas mana pun. Misalkan titik sudut terdekat V ditemukan pada sisi batas AB dan periksa apakah segmen BV dan VA tidak memotong sisi batas lainnya. Kemudian kita akan membuat segitiga ABV dan memindahkan tepi AB ke kategori tidak aktif. Jika tidak ada tepi BV di antara tepi batas, maka kita akan membuat tepi batas baru pada segmen VB, tetapi jika ada tepi BV di antara tepi batas, maka kita akan memindahkannya dan simpul B ke kategori tidak aktif. Jika tidak ada tepi VA di antara tepi batas, maka kita akan membuat tepi batas baru pada segmen AV, tetapi jika ada tepi VA di antara tepi batas, maka kita akan memindahkannya dan simpul A ke kategori tidak aktif.

Jika suatu segmen atau VA memotong sisi batas lainnya, maka kita lanjutkan mencari titik terdekat untuk sisi batas lainnya. Triangulasi akan selesai setelah semua sisi dan simpul diklasifikasikan tidak aktif.

Beras. 9.7.7. Triangulasi dengan metode koreksi

Pada Gambar. 9.7.7 menunjukkan triangulasi permukaan dengan mengoreksi segitiga pada sel yang berpotongan dengan kontur batas. Pada Gambar. 9.7.8, menggunakan triangulasi yang dihasilkan, permukaan itu sendiri ditampilkan.

Jika poligon batas dan permukaannya mempunyai simetri tertentu, maka triangulasi dengan metode koreksi akan mempunyai simetri yang serupa.

Triangulasi dengan metode absorpsi.

Mari kita pertimbangkan metode triangulasi lainnya. Dari segi kecepatan kalah dengan triangulasi Delaunay dan modifikasinya. Untuk memulai prosedur triangulasi, batas permukaan perlu direpresentasikan dalam bentuk poligon tertutup. Selama proses triangulasi, kita perlu menentukan langkah-langkah berdasarkan parameter permukaan. Dengan arah gerak yang diketahui, langkah-langkah tersebut ditentukan oleh rumus (9.4.6). Perkiraan langkah untuk parameter permukaan dapat ditemukan sebagai berikut. Mari kita definisikan suatu wilayah pada bidang parameter di sekitar titik tertentu sedemikian rupa sehingga setiap segmen spasial dari titik ke titik di wilayah ini tidak akan lebih jauh dari nilai tertentu S dari permukaan.

Untuk melakukan ini, kami menghitung kenaikan parameter yang diizinkan di sepanjang garis koordinat

dimana adalah koefisien bentuk kuadrat pertama dan kedua permukaan di titik . Sebagai batas daerah yang diinginkan, kita akan mengambil elips yang berpusat di suatu titik dan sumbu semi. Elips ini memiliki persamaan

Jika Anda ingin mencari titik pada bidang di sebelah titik pada arah yang ditentukan oleh sudut dengan sumbu dan, maka parameternya adalah

Pertama, mari kita pertimbangkan kasus yang lebih sederhana ketika luas parameter permukaan dibatasi pada satu kontur eksternal. Kami memperkirakan batas permukaan dengan poligon tertutup pada domain parametrik. Saat membuat triangulasi, kita akan menggunakan poligon kerja, yang dalam hal ini kita akan mengambil sebagai poligon kontur luar. Kita akan menambahkan titik poligon ke array titik dua dimensi yang dihasilkan. Kita akan membuat segitiga dari tepi area kerja, mempersempitnya hingga hanya tersisa tiga titik di area kerja.

Mari kita cari titik sudut pada poligon kerja yang berubah menjadi daerah. Titik seperti itu selalu ada dan sudut rotasinya lebih kecil. Mari kita nyatakan titik ini dengan O, dan parameternya dengan Dekat titik ini kita akan membuat satu atau dua segitiga, bergantung pada sudut rotasi. Jika sudutnya lebih kecil, maka kita akan membuat satu segitiga pada ketiga titik tersebut (Gbr. 9.7.9). Jika tidak, kita akan membuat dua segitiga pada titik ini, dua titik bertetangga dan satu titik baru (Gbr. 9.7.11). Titik baru tersebut dilambangkan dengan P. Kita cari titik P pada diagonal jajar genjang B OS P. Jika titik puncak jajar genjang terletak di dalam elips (Gbr. 9.7.10), maka kita anggap sebagai titik P . Jika tidak, kita akan mengambil perpotongan elips dan diagonal jajar genjang sebagai titik P . Dalam kasus terakhir, sama sekali tidak perlu mencari perpotongan elips dan segmen.

Koordinat titik P ditentukan melalui koordinat titik O BC

Sudut ruas OP dengan horizontal ditentukan oleh persamaan

(9.7.8)

Data ini memungkinkan untuk menentukan posisi titik P relatif terhadap elips (9.7.5).

Dalam kasus yang ditunjukkan pada Gambar. 9.7.9, mari kita buat sebuah segitiga (ingat jumlah titik sudutnya) dan hapus titik O pada area kerja. 9.7.11, kita akan membuat dua segitiga dan di area kerja kita akan mengganti titik O dengan titik P dan menempatkan titik terakhir dalam susunan titik yang dihasilkan. Pada Gambar. Gambar 9.7.12 menunjukkan poligon yang diperoleh setelah membuat dua segitiga dan menghilangkan titik O. Dalam kedua kasus, titik O akan dikeluarkan dari poligon kerja dan poligon kerja akan menyempit. Perhatikan bahwa segitiga hanya dapat dibuat jika luas kerjanya, setelah menyempit, tidak berpotongan dengan sendirinya.

Beras. 9.7.9. Membangun segitiga

Beras. 9.7.10. Poligon hasil

Beras. 9.7.11. Konstruksi dua segitiga

Beras. 9.7.12. Poligon hasil

Situasi seperti itu ditunjukkan pada Gambar. 9.7.13. Hal ini dapat terjadi ketika sisi-sisi segitiga yang dibangun berpotongan dengan sisi-sisi area kerja yang tidak berdekatan dengannya. Sebelum membuat segitiga baru seperti pada kasus yang ditunjukkan pada Gambar. 9.7.9, dan dalam kasus yang ditunjukkan pada Gambar. 9.7.11, pemeriksaan harus dilakukan untuk memastikan bahwa poligon yang dihasilkan tidak berpotongan.

Selain itu, dalam menentukan posisi titik P, yang penting adalah jaraknya cukup dari titik-titik lain pada area kerja dan tidak mendekati ruas-ruas yang menghubungkan titik-titik pada area tersebut. Jika tidak, kesulitan mungkin timbul di kemudian hari saat membuat segitiga. Oleh karena itu, sebelum mempersempit poligon yang berfungsi, Anda harus memeriksa poligon yang dihasilkan untuk perpotongan sendiri. Jika tidak mungkin membuat segitiga (segitiga) di dekat titik O, maka Anda harus mencari titik lain di mana poligon lebih banyak membungkus kontur di dalam kontur daripada yang lain, dan melakukan tindakan yang dijelaskan di sana.

Selanjutnya, dengan area kerja yang dimodifikasi, kami akan melakukan tindakan yang sama seperti yang baru saja kami jelaskan. Mari kita cari titik dalam poligon kerja yang lebih banyak belokannya ke dalam area daripada titik lainnya, periksa kemungkinan mempersempit poligon di dalamnya dengan membuat satu atau dua segitiga dan mempersempit poligon.

Beras. 9.7.13. Anda tidak dapat membuat segitiga di sudut ini

Melanjutkan proses ini, kita akan memperluas susunan titik dua dimensi dan susunan segitiga, dan pada saat yang sama kita akan mempersempit poligon yang berfungsi, mengurangi luas yang dicakupnya dan jumlah titiknya. Pada tahap tertentu dari tindakan ini kita akan mendapatkan poligon kerja yang terdiri dari tiga titik. Mari kita buat segitiga terakhir pada titik-titik ini, hilangkan area kerja dan selesaikan triangulasi. Dalam metode triangulasi yang dijelaskan, luas yang dibatasi oleh wilayah kerja seolah-olah dihilangkan dengan memotong segitiga darinya.

Mari kita perhatikan kasus umum ketika luas parameter permukaan dibatasi oleh satu kontur luar dan beberapa kontur dalam yang seluruhnya terletak di dalam kontur luar. Kami memperkirakan batas permukaan dengan poligon tertutup pada domain parametrik. Untuk setiap kontur kita akan membuat poligon kita sendiri. Sama seperti kontur, untuk poligon yang dibangun di atasnya, aturan orientasi timbal baliknya harus dipenuhi. Orientasi poligon bagian dalam harus berlawanan dengan orientasi poligon bagian luar. Mari kita mulai membuat triangulasi dengan poligon kontur luar. Mari kita masukkan titik-titiknya ke dalam susunan titik dua dimensi yang dihasilkan, dan buat poligon itu sendiri menjadi poligon yang berfungsi.

Kita akan membuat segitiga dengan cara yang sama seperti pada kasus daerah terhubung sederhana. Mari kita cari titik O pada area kerja, periksa kemungkinan penyempitan area kerja disana, dan persempit area tersebut. Jika terdapat kontur internal, akan lebih sulit untuk memeriksa kemungkinan penyempitan area kerja pada titik yang dipilih. Selain pemeriksaan yang dijelaskan untuk perpotongan sisi-sisi segitiga dengan sisi-sisi area kerja, perlu juga untuk memeriksa perpotongan sisi-sisi segitiga dengan sisi-sisi semua poligon dalam.

Mari kita periksa kemungkinan membangun dua segitiga di titik O (Gbr. 9.7.11), dan temukan bahwa titik P yang baru, setelah dibangun, akan berada di dalam salah satu poligon internal atau akan berada dalam jarak yang tidak dapat diterima dengan segmennya. Dalam hal ini, kita tidak akan membuat titik P, namun akan memasukkan poligon internal ini ke dalam poligon kerja dengan membuat dua segitiga yang ditunjukkan pada Gambar. 9.7.14.

Untuk memasukkan titik-titik salah satu poligon dalam ke dalam poligon kerja, kita mencari di antara titik-titik poligon dalam suatu titik yang paling dekat dengan titik C (berdekatan dengan titik O) dari poligon kerja.

Mari kita buat segitiga di titik OCF dan CEF dan di antara titik O dan C area kerja masukkan titik-titik poligon dalam, mulai dari titik F dan diakhiri dengan titik E. Jadi, kita akan membagi area kerja menjadi segmen OS, pecahkan poligon internal pada segmen EF dan satukan dengan segmen OF dan EU.

Beras. 9.7.14. Konstruksi dua segitiga

Beras. 9.7.15. Menggabungkan poligon eksternal dan internal

Hasil penggabungan ditunjukkan pada Gambar. 9.7.15. Tentu saja, sebelum menggabungkan poligon luar dan dalam, pemeriksaan harus dilakukan untuk memastikan kebenaran operasi ini.

Selanjutnya, kami akan terus mempersempit area kerja dengan cara yang dijelaskan hingga kami berada di dekat area internal lain dan memasukkannya ke dalam area kerja. Akibatnya, semua poligon internal akan dimasukkan ke dalam poligon kerja, yang harus dipersempit menjadi tiga titik terakhir. Akibatnya, seluruh wilayah perkalian yang terhubung untuk menentukan parameter permukaan akan ditutupi dengan segitiga.

Beras. 9.7.16. Anda tidak dapat membuat segitiga di sudut ini.

Mungkin ada situasi ketika tidak mungkin membuat segitiga tunggal pada poligon tertentu. Pada Gambar. Gambar 9.7.16 menunjukkan suatu area yang dibatasi oleh dua poligon yang masing-masing terdiri dari empat segmen. Untuk poligon luar, kita tidak dapat melanjutkan triangulasi karena poligon dalam menghalangi. Dalam hal ini, kita akan menemukan dua titik tetangga B dan C dari poligon, yang untuknya kita dapat membuat segitiga HRV. Titik P diproyeksikan ke tengah sisi BC dan terletak pada jarak tertentu sehingga segitiga baru tidak memotong poligon.

Metode triangulasi lainnya.

Ada cara triangulasi lainnya. Misalnya, setelah membuat poligon kontur luar dan dalam dari luas definisi permukaan, strategi berbeda untuk membuat segitiga dapat dipilih. Pilihan lainnya adalah menggabungkan poligon luar dan dalam menjadi satu poligon sebelum memulai triangulasi. Anda dapat "membuat sketsa" titik-titik di dalam area definisi parameter menggunakan algoritma tertentu dan melakukan triangulasi Delaunay menggunakan titik-titik tersebut dan titik-titik poligon kontur batas. Ada algoritma yang pertama-tama membuat segitiga besar dan kemudian membaginya menjadi ukuran yang bisa diatur.

Triangulasi tubuh.

Triangulasi suatu benda adalah sekumpulan segitiga yang diperoleh dengan melakukan triangulasi pada permukaan mukanya. Triangulasi permukaan individu berbeda dari triangulasi permukaan benda karena dalam kasus terakhir, poligon batas untuk permukaan yang berdekatan harus konsisten (Gbr. 9.7.17).

Beras. 9.7.17. Konsistensi Poligon Batas Wajah Badan

Bagian-bagian poligon dari permukaan-permukaan yang berdekatan yang melewati sepanjang tepi yang sama akan konsisten jika titik-titiknya bertepatan dalam ruang.

Penerapan triangulasi.

Segitiga yang dibangun sebagai hasil triangulasi digunakan untuk memperoleh gambar nada. Pada Gambar. 9.7.18 dan 9.7.19 menunjukkan triangulasi muka badan lembaran, gambar nadanya ditunjukkan pada Gambar. 6.5.1.

Beras. 9.7.18. Triangulasi wajah tubuh menggunakan metode koreksi

Mempartisi domain penentuan parameter permukaan menjadi segitiga dapat digunakan dalam integral (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) saat menghitung karakteristik geometri benda . Selama integrasi numerik, langkah parametrik untuk kurva harus dihitung menggunakan rumus (8.11.5), dan untuk permukaan, langkah parametrik harus dihitung menggunakan rumus (8.11.1) dan (8.11.2).