Pembuat Triangulasi Delaunay

Pembuat Triangulasi Delaunay mengubah sekumpulan titik 2D apa pun menjadi triangulasi unik yang memaksimalkan sudut interior terkecil — standar utama untuk pemodelan medan, pembuatan mesh elemen hingga, interpolasi tetangga terdekat, dan kelas geometri komputasi. Tempel koordinat (atau pilih pola mulai cepat), dan alat ini akan menjalankan algoritma Bowyer-Watson di sisi server, mewarnai setiap segitiga berdasarkan kualitasnya, serta menampilkan sifat lingkaran luar kosong, lambung cembung, dan dual Voronoi sesuai permintaan.

Cara Membaca Mesh yang Dihasilkan

Apa yang Membuat Pembuat Triangulasi Delaunay Ini Berbeda

Apa Itu Triangulasi Delaunay?

Diberikan sekumpulan titik 2D, biasanya ada banyak cara untuk menghubungkannya menjadi sebuah triangulasi (pemasangan ubin lengkap pada lambung cembungnya oleh segitiga-segitiga tanpa ada tumpang tindih atau celah). Triangulasi Delaunay, dinamai dari matematikawan Rusia Boris Delaunay (1934), adalah salah satu yang memenuhi sifat lingkaran luar kosong: untuk setiap segitiga dalam mesh, lingkaran yang melewati ketiga verteksnya tidak berisi titik masukan lainnya. Sifat tunggal ini memiliki konsekuensi yang luar biasa: di antara semua triangulasi dari kumpulan titik yang sama, triangulasi Delaunay memaksimalkan sudut interior terkecil. Sederhananya, ini menghasilkan segitiga yang paling "gemuk" dan "seimbang" yang dimungkinkan.

Cara Kerja Algoritma Bowyer-Watson

1. Kelilingi semua titik masukan dengan super-segitiga yang sangat besar.
2. Masukkan satu titik masukan secara bergantian. Untuk setiap titik baru, cari setiap segitiga yang ada yang lingkaran luarnya berisi titik baru tersebut — ini disebut sebagai segitiga "buruk".
3. Hapus segitiga buruk tersebut. Lubang yang ditinggalkan memiliki batas poligonal.
4. Hubungkan titik baru ke setiap sisi dari batas tersebut, membentuk segitiga baru.
5. Setelah semua titik dimasukkan, hapus semua segitiga yang masih menyentuh verteks super-segitiga. Yang tersisa adalah triangulasi Delaunay dari kumpulan titik aslinya.

Di Mana Triangulasi Delaunay Digunakan

• Pemodelan medan (GIS): sampel elevasi (biasanya berjarak tidak teratur, seperti stasiun medan) dihubungkan menjadi Triangulated Irregular Network (TIN) untuk kueri elevasi, pembayangan, dan visualisasi 3D.
• Analisis elemen hingga: segitiga Delaunay yang terbentuk dengan baik menghasilkan solusi numerik yang stabil untuk persamaan diferensial parsial dalam mekanika, perpindahan panas, dan elektromagnetik.
• Grafik komputer: pembuatan mesh untuk perendeman (rendering), rigging karakter, dan medan prosedural — jaminan "tanpa segitiga pipih" dari Delaunay menghindari artefak peregangan tekstur.
• Interpolasi tetangga alami: permukaan halus direkonstruksi dari sampel yang tersebar dengan menghitung tetangga alami dari setiap titik kueri melalui dual Voronoi.
• Kelas geometri komputasi: sebuah algoritma kanonis dengan hubungan mendalam ke lambung cembung, diagram Voronoi, lokasi titik, dan divide-and-conquer.
• Pengiris cetak 3D dan jalur alat CNC: Delaunay 2D (dan kerabat 3D-nya, tetrahedralisasi Delaunay) mendasari banyak strategi pengirisan dan pengisian (infill).

Delaunay vs Voronoi: Dua Sisi dari Koin yang Sama

Diagram Voronoi membagi bidang menjadi satu sel per titik masukan, di mana setiap sel berisi semua hal yang lebih dekat ke titiknya daripada ke titik lainnya. Hubungkan titik-titik yang selnya berbagi batas, dan Anda akan mendapatkan triangulasi Delaunay yang tepat. Sebaliknya, pusat lingkaran luar dari segitiga Delaunay yang berdekatan, jika dihubungkan oleh segmen garis, akan membentuk sisi Voronoi. Aktifkan "Dual Voronoi" pada alat ini untuk melihat garis putus-putus oranye yang ditumpangkan pada grafik yang sama — setiap sisi Delaunay memotong tepat satu sisi Voronoi pada sudut siku-siku.

Kualitas, Segitiga Pipih, dan Penyempurnaan Mesh

Delaunay memaksimalkan sudut interior minimum global, tetapi tidak dapat memperbaiki distribusi titik yang pada dasarnya buruk. Jika titik masukan Anda hampir kolinear, berkluster, atau menyisakan wilayah kosong yang besar, beberapa segitiga akan tetap pipih (sudut minimum di bawah 20°). Solusinya adalah penyisipan titik Steiner: algoritma seperti algoritma Ruppert dan algoritma kedua Chew secara iteratif menambahkan titik baru di pusat lingkaran luar segitiga pipih, melakukan triangulasi ulang setiap kali, hingga setiap segitiga memenuhi batas kualitas target. Generator ini menunjukkan kepada Anda segitiga mana yang pipih sehingga Anda tahu di mana harus menambahkan titik Steiner jika Anda menginginkan mesh yang lebih halus.

Contoh Terbimbing

Klik preset "Lingkaran + pusat". Alat ini menempatkan 18 titik di sekitar lingkaran dan 1 titik di tengah, lalu membuat triangulasinya. Hasilnya adalah susunan sempurna dari 18 segitiga sama kaki yang bertemu di pusat — masing-masing memiliki sudut 10° di bagian tepi dan 80°–80° di bagian pusat. Sudut minimum terburuk adalah 10°, semua segitiga ditandai sebagai pipih, dan histogram menunjukkan semuanya berada dalam kategori 0°–10°. Contoh ini adalah kasus pembelajaran yang bagus: bahkan triangulasi optimal Delaunay pun dapat memiliki segitiga pipih ketika masukan memaksanya. Sekarang klik "Awan acak" — algoritma yang sama menghasilkan segitiga yang terbentuk dengan baik karena titik-titiknya tersebar merata, dan histogram bergeser ke kanan.

Kesalahpahaman Umum

• "Triangulasi Delaunay itu unik": biasanya ya, tetapi jika empat titik masukan berada dalam satu lingkaran yang sama (co-circular), ada dua triangulasi Delaunay yang valid untuk kelompok tersebut. Generator memilih salah satu secara konsisten.
• "Lebih banyak titik selalu berarti kualitas yang lebih baik": menambahkan titik yang ditempatkan dengan buruk dapat memunculkan segitiga pipih baru. Algoritma titik Steiner menempatkan titik baru dengan hati-hati — di pusat lingkaran luar — sehingga kualitas dijamin akan meningkat.
• "Delaunay sama dengan lambung cembung": tidak. Lambung cembung adalah batas luar; triangulasi Delaunay mengisi bagian dalam dengan segitiga.
• "Semua triangulasi terlihat hampir sama": perbedanyya sangat dramatis. Sebuah "peralihan sisi" dari sisi Delaunay dapat mengubah segitiga 25° menjadi segitiga 5°. Heatmap kualitas dari alat ini membuat perbedaan tersebut terlihat jelas.

Pertanyaan yang Sering Diajukan