Algoritma untuk membuat segitiga yang berdekatan

Saya memiliki sistem di mana Anda dapat mengklik sekali untuk menempatkan sebuah simpul dalam sebuah adegan. Ketika Anda menempatkan 3 node, itu membentuk segitiga. Ketika Anda menempatkan node masa depan, itu menciptakan segitiga baru dengan menggabungkan node itu ke 2 node terdekat yang ada.

Ini berfungsi dengan baik sebagian besar waktu tetapi cacat ketika digunakan di dekat segitiga dengan sudut yang sangat akut, karena salah satu dari 2 node terdekat sering bukan salah satu yang harus digunakan.

Sebagai contoh, lihat gambar di bawah ini. Segitiga magenta adalah yang pertama ditempatkan. Jika saya klik pada posisi bertanda X, yang saya dapatkan adalah segitiga baru di mana overlay biru berada. Yang saya inginkan adalah segitiga baru di mana overlay hijau berada. (mis. simetris dengan magenta, dalam contoh ini. Klarifikasi: Segitiga hijau dan magenta tidak tumpang tindih - yang hijau memanjang di bawah yang biru ke simpul paling kiri)

Bagaimana saya bisa menentukan 2 simpul yang ada untuk digunakan saat membuat segitiga baru sehingga segitiga tidak ditumpangkan seperti ini?

EDIT : Mencari tepi terdekat memberikan hasil yang lebih baik , tetapi tidak sempurna. Pertimbangkan situasi ini:

Tes 'tepi terdekat' adalah ambigu, dan dapat mengembalikan AB atau AC (sebagai titik terdekat ke X untuk keduanya adalah pada A). Hasil yang diinginkan adalah AC, untuk membentuk segitiga ACX tanpa ujung yang tumpang tindih. Bagaimana saya bisa memastikan hasil ini? (Saya lebih suka tidak harus melakukan tes tumpang tindih masing-masing tepi sebagai tie-breaker jika memungkinkan karena saya khawatir bahwa tes tepi terdekat tidak harus melihat 2 persis sama, mengingat masalah presisi titik mengambang.)

Daripada menemukan jarak minimum ke node, cari jarak minimum ke tepi (yaitu segmen garis yang ditentukan oleh node).

Kemudian, jika titik terdekat adalah titik (yang Anda harus menggunakan beberapa tes titik mengambang epsilon **), bandingkan sudut antara garis dari titik baru ke titik dan masing-masing tepi terhubung ke titik itu. Pilih satu dengan sudut absolut minimum:

MinAngle(newPoint, vertex, edge1, edge2)
{
   newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
   edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
   edge2Unit = norm(edge2 - vertex);

   edge1Dot = dot(edge1Unit, newEdgeUnit);
   edge2Dot = dot(edge2Unit, newEdgeUnit);

   // you can simply compare dot products to find the minimum absolute angle
   if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
   return edge2;
}

** Untuk menghindari penambahan segitiga yang merosot, yang dapat mengganggu tes epsilon, Anda mungkin ingin menempatkan wilayah di sekitar setiap titik di mana menambahkan poin tidak diizinkan, (seperti melarang poin dalam beberapa beberapa epsilon yang digunakan di atas).

Setelah segitiga pertama ditempatkan, saat menempatkan simpul baru, Anda akan selalu menghasilkan dua tepi baru. Tepi ketiga untuk segitiga baru akan selalu menjadi tepi bersama dengan segitiga sebelumnya. Jika Anda dapat menemukan cara untuk menentukan tepi bersama, Anda akan tahu simpul mana yang harus disambungkan, tetapi itulah bagian yang sulit. Saya percaya satu cara Anda bisa melakukan ini dengan menggambar garis dari titik baru Anda ke pusat masing-masing dari tiga tepi terakhir yang dihasilkan (atau mungkin 3 tepi terdekat).

Jika garis dari titik Anda ke pusat tepi tidak melewati salah satu dari dua tepi lainnya, Anda memiliki tepi yang Anda bagikan. Tepi yang dibagikan akan memberi tahu Anda dua simpul mana yang harus disambungkan ke simpul baru Anda.

Jimmy membawa kasing untuk titik yang tidak jelas ke mana segitiga baru akan pergi seperti ini:

Itu akan memberi Anda kesempatan untuk memilih antara dua segitiga yang valid. Mungkin yang memutuskan titik tengah mana yang paling dekat.

Mempertimbangkan pembaruan Anda, meski lebih kompleks, solusi saya hanya akan menghasilkan dasi ketika Anda memiliki dua segitiga yang valid. Dengan menggunakan metode ini, contoh gambar kedua Anda akan menghasilkan hasil yang Anda inginkan.

Memiliki segitiga ABC magenta Anda, Anda kemudian memasukkan simpul X baru. Saya pikir jelas bahwa akan ada dua garis mulai dari D yang tidak akan berpotongan di antara salah satu tepi ABC segitiga.

Dua baris ini bisa menjadi AX & BX, BX & CX atau AX & CX. Anda kemudian dapat memperlakukan masalah Anda sebagai masalah klasik "do two lines intersect"? Anda kemudian dapat memeriksa pasangan garis mana yang tidak bersinggungan dengan tepi segitiga ABC mana saja yang mengikuti, misalnya, salah satu metode dari pertanyaan ini . Oleh karena itu, Anda akan memiliki dua tepi baru dari segitiga baru.

Mencari tahu jika Anda berada di salah satu daerah yang tidak ambigu (1, 2, 3 di bawah), cukup mudah: perlakukan setiap tepi segitiga Anda sebagai bidang 2D dan uji sisi mana pesawat pada titik baru Anda berada. Jika Anda berada di dalam dua dari mereka tetapi di luar satu, maka yang sesuai dengan tepi segitiga yang berkontribusi dua simpul untuk segitiga baru Anda.

Jika Anda berada di dalam satu dan di luar dua, Anda berada dalam kasus ambigu di mana bagian terdekat dari segitiga ke titik baru Anda adalah sudut. Dalam hal ini, Anda bisa membentuk bidang 2D dari titik tengah dari tepi yang berlawanan (yang Anda berada di dalamnya) dan verteks terdekat (yang dibagi oleh dua pesawat yang Anda berada di luar). Anda dapat memilih ujung tergantung pada sisi mana dari pesawat ini titik baru Anda aktif.

Perhatikan bahwa tes bidang dalam 2D ​​bekerja dengan cara yang sama seperti dalam 3D: beri titik vektor dari mana saja pada bidang ke titik Anda dengan bidang normal (dalam 2D, ini garis tegak lurus).

(Kebetulan, daerah yang dibatasi magenta dalam gambar ini disebut daerah Voronoi; mereka adalah area ruang yang mengandung titik-titik yang paling dekat dengan fitur tertentu — tepi atau simpul-segitiga). Sunting: Terminologi saya di sini sebenarnya tidak cukup benar, ini bukan daerah Voronoi.)