Bagaimana cara menemukan titik terdekat (dengan demikian membentuk poligon) melampirkan titik tertentu? (Lihat gambar)

8

Saya bekerja dengan mesin game, dan tugas saya adalah menambahkan kode untuk mensimulasikan fraktur jerat kaku.

Saat ini aku hanya berusaha memecahkan kubus.

Saya menggunakan algoritma Voronoi untuk membuat pecahan (realistis) retak dan saya menggunakan metode setengah-pesawat untuk menghasilkan sel Voronoi.

untuk menemukan titik terdekat (dilingkari merah) di sekitar Voronoi (titik ungu)

Sekarang cara saya melakukan ini adalah untuk setiap titik benih, saya membuat pesawat yang merupakan bidang garis lurus (garis hitam lurus pada gambar) dengan sisa titik benih dan saya menghitung persimpangan semua pesawat ini untuk memberi saya poin yang berbeda ( semua titik oranye).

Saya sudah sejauh ini.

Dari semua titik persimpangan yang dihitung ini, saya hanya membutuhkan titik-titik yang terdekat dan melampirkan titik benih (titik-titik yang dilingkari merah) dan saya perlu membuang sisanya.

Informasi yang saya miliki:

1) Persamaan bidang semua pesawat (ditentukan oleh vektor normal yang dinormalisasi dan jaraknya dari tempat asal)

2) Titik persimpangan (yang saya hitung)

Adakah yang bisa membantu saya mencari tahu bagaimana saya bisa menemukan poin yang dikelilingi warna merah?

c++ vector intersection nilspin
sumber
Tidak ada jawaban, tapi itu masalah yang menarik!
Tim Holt

Jawaban:

4

Mengikuti metode setengah-bidang , Anda akan menemukan segmen garis ke setiap titik lain dan garis-garis tegak lurus masing-masing

langkah 1: segmen garis langkah 2: garis-garis tegak lurus

yang kemudian Anda potong untuk menemukan simpul potensial dari sel Voronoi.

Sekarang, Anda ingin mengecualikan orang-orang yang memotong salah satu dari setengah-pesawat "jauh" yang dibentuk oleh garis-bagi.

Dua persimpangan yang cocok, satu persimpangan

Saya mewarnai pesawat setengah jauh "jauh" biru tembus untuk kejelasan.

Di sini, dua titik merah yang dilingkari lulus tes: Mereka tidak berada dalam setengah-bidang. The titik merah dilingkari tidak lulus, karena itu dalam setengah-bidang yang dibentuk menuju titik di kanan atas.

Ini secara efektif berarti menguji apakah setiap titik ada di sisi lain dari setiap garis garis bagi (relatif terhadap situs Voronoi) dan membuang titik-titik yang ada. (Waspadalah terhadap kesalahan pembulatan.)

Anko
sumber
Jawaban ini sangat bermanfaat. Untuk memeriksa apakah kedua titik terletak di sisi yang sama dari bidang saya menggantikan vektor dalam persamaan bidang dan mencari tanda-tanda mereka. Jika keduanya positif / negatif, maka mereka berada di sisi yang sama. Jika tidak, mereka berada di sisi yang berlawanan. Ini bekerja! Kode saya tampaknya menghasilkan simpul yang benar untuk pecahan Voronoi akhirnya!
nilspin
program apa yang Anda gunakan untuk menghasilkan gambar-gambar itu dalam jawaban Anda?
nilspin
@nilspin Inkscape .
Anko
3

Anda dapat dengan mudah mengulangi tepi dan menyaring semua simpul yang tidak dalam setengah bidang yang sama dengan tempat menarik.

Sebagai pengoptimalan, beralih dari tepi terdekat ke terjauh. Saya pikir Anda bahkan dapat menyaring simpul saat menghasilkan irisan.

Itu seperti mengiris pai dengan pisau tak berujung, sampai hanya sepotong kecil yang tersisa dengan ceri. Jika Anda menyukai analogi. Cukup potong dan lihat bagian mana yang akan diambil dan mana yang akan dibuang.

Shadows In Rain
sumber