Bagaimana saya bisa tahu apakah suatu benda bergerak CW atau CCW di sekitar jalur yang terhubung?

19

Katakanlah kita memiliki bentuk bergerigi:

bentuk0

Dan dua makhluk bergerak di sepanjang garis besarnya.

Lalu kami menghaluskan bentuk sepenuhnya dengan menarik sudut keluar.

Kami mendapatkan ini:

halus

Sangat mudah untuk melihat sekarang bahwa Orange bergerak CW dan CCW hijau. Bagaimana saya bisa tahu ke arah mana mereka bergerak tanpa menghaluskan bentuknya?

Gambar baru

masukkan deskripsi gambar di sini

serigala
sumber
Ini 2 sen saya: i.imgur.com/zrBdw.png
Kendall Frey

Jawaban:

27

Gambar garis hingga tak terbatas dan hitung berapa kali Anda melewati bentuk (genap atau ganjil), tidak termasuk segmen tempat makhluk itu berada. Kemudian periksa apakah makhluk itu pergi ke kiri atau kanan garis itu.

contoh

Dalam contoh ini, kami menyilangkan bentuk dua kali (bahkan genap) dan kami pergi ke kiri. Hasilnya langsung dari tabel ini:

   # Crosses | even  | odd
  Direction  |       |
-------------+-------+------
    left     | CCW   |  CW
    right    |  CW   | CCW

Dalam pseudocode:

x, y = position of creature
vx, vy = direction of creature movement
crossings = 0
for each x1, y1, x2, y2 in shape segments:
    if (x1 < x and x <= x2) or (x2 < x and x <= x1):
        if y - y1 > (x - x1) * (y2 - y1) / (x2 - x1):
            ++crossings
if (crossings & 1) == (vx < 0):
    return CW
else
    return CCW
sam hocevar
sumber
apakah Anda menyertakan makhluk garis yang bergerak?
Ali1S232
@ Gajoo: tidak, maka> bukan> = pada baris 6. Saya akan menambahkan catatan tentang ini. Tetapi perhatikan bahwa Anda bisa menyertakan baris, dan hanya membalikkan isi tabel.
sam hocevar
1
Saya menyerah antara memberi jawaban berdasarkan metode ini, dan jawaban yang saya berikan. Saya senang kami memiliki kedua pendekatan yang diwakili di sini. Yang satu ini secara konseptual lebih sederhana dan sangat elegan, tetapi membutuhkan pengujian garis segmen, yang mungkin sulit untuk membuatnya kuat.
Trevor Powell
@TrevorPowell Benar. Menemukan ujung terjauh bisa membingungkan. Saya memeriksa pertama berdasarkan sudut paling jauh dari tepi dan kemudian saya dengan menggambar garis dari pusat bentuk dan melalui pusat dua sisi (dua yang berbagi titik) dan melihat apakah salah satu garis melintasi tepi lain dalam perjalanan ke tak terbatas setelah melewati salah satu sisi ini. Itu bekerja dengan baik
wolfdawn
5

Itu tergantung pada informasi apa yang Anda miliki dari struktur data bentuk Anda, tetapi makhluk yang memindahkan CW di sepanjang garis bentuk akan selalu memiliki bagian dalam bentuk di sebelah kanannya, dan makhluk yang bergerak CCW akan memiliki bagian dalam bentuk di kirinya.

Jeff
sumber
Solusi yang jauh lebih sederhana, dan juga pemikiran pertama saya.
Amplify91
bagaimana Anda tahu arah mana yang ada di dalam bentuk? Maksud saya bergerak di sepanjang tepi bagian dalam bentuk ada di kiri atau kanan. bagaimana kamu tahu ke mana itu?
Ali1S232
Solusi yang sangat elegan, tetapi tidak benar secara umum. Bayangkan donat, diratakan di atas meja untuk membuat bentuk dua dimensi. Anda dapat berjalan di sepanjang tepi bentuk ini, menjaga bagian dalam bentuk di sebelah kiri Anda dan membuat putaran searah jarum jam atau berlawanan arah jarum jam tergantung di mana Anda mulai.
Marcks Thomas
4
  1. Hitung titik tengah bentuk Anda.
  2. Pilih tepi bentuk Anda yang paling jauh dari tengah.
    • (Memilih tepi yang paling jauh memastikan bahwa Anda tidak mulai dari bagian cekung yang terbalik, yang akan menghasilkan penentuan searah jarum jam / berlawanan arah jarum jam ke belakang untuk seluruh bentuk)
  3. Tentukan arah mana di sepanjang tepi itu searah jarum jam
    • (Implementasi sederhana ini akan melibatkan membandingkan sudut dari pusat bentuk ke setiap ujung tepi yang dipilih. Tanda perbedaan antara sudut akan memberi tahu Anda arah jarum jam vs berlawanan arah jarum jam)
  4. Iterasi semua tepi bentuk, mulai dari tepi yang Anda pilih pada langkah 2, buat daftar tepi. Untuk setiap tepian, simpan dua simpulnya secara searah jarum jam.
    • (Jika bentuk Anda tidak berubah seiring waktu, maka Anda dapat menyimpan daftar tepi ini untuk digunakan nanti, sehingga Anda tidak perlu melakukan empat langkah pertama setiap frame)
    • (Anda mungkin sudah memiliki daftar tepi. Jika demikian, Anda dapat menyimpan urutan simpul searah jarum jam ini dalam daftar yang sama.)
  5. Untuk menentukan apakah suatu entitas bergerak searah atau berlawanan arah jarum jam:
    • Tentukan sisi mana entitas bergerak.
    • Lakukan produk titik dari arah gerakan entitas terhadap vektor dari simpul start-> end searah jarum jam yang Anda tentukan kembali pada langkah 4.
    • Jika hasil dari produk titik adalah nilai lebih besar dari nol, entitas bergerak searah jarum jam. Kurang dari nol berarti berlawanan arah jarum jam.
Trevor Powell
sumber
Jawaban yang sangat cerdas
wolfdawn
Saya punya pertanyaan kecil? dengan asumsi simpul dalam bentuknya diberi nomor mulai dari titik paling kiri CWW, berdasarkan jawaban Anda bagaimana saya bisa tahu jika bergerak dari 6-> 7 atau 9-> 10 (berbasis nol) bergerak searah jarum jam?
Ali1S232
Anda mulai dengan tepi paling jauh, dan mencari tahu arah mana yang searah jarum jam di tepi itu. Katakanlah tepi A searah jarum jam dari titik 'a' ke 'b'. Kemudian jika kita pindah ke tepi B (yang memiliki simpul 'b' dan 'c'), kita tahu bahwa B searah jarum jam dari 'b' ke 'c'. Demikian pula, tepi C akan searah jarum jam dari 'c' ke 'd'. Setelah kita mengetahui arah searah jarum jam yang benar dari satu sisi (langkah 1-3), dengan melanjutkan ke arah searah jarum jam di sekitar tepi bentuk, kita dapat menyimpulkan arah 'searah jarum jam' yang benar untuk setiap sisi, tanpa benar-benar melihat di mana ujungnya berada, jadi cekung tidak masalah.
Trevor Powell
bagaimana Anda bisa tahu apakah edge A searah jarum jam dari 'a' ke 'b' atau jika searah jarum jam dari 'b' ke 'a'? Saya pikir Anda melewatkan bagian itu.
Ali1S232
@ Gajoo Itulah titik kurung pada langkah 3. Mungkin seharusnya tidak menjadi tanda kurung, karena itu benar-benar langkah kritis dari seluruh proses.
Trevor Powell
2

Anda harus tahu ke arah mana poligon didefinisikan, ke arah mana simpul mengitarinya.

Jika Anda tidak tahu ini, Anda bisa mengatasinya dengan menghitung luas poligon:

float Polygon::area() {
    float result = 0.0f;

    for(int a = 0; a < vertexCount; a ++) {
        int b = (a+1) % vertexCount;
        result += vertices[a].x * vertices[b].y;
        result -= vertices[a].y * vertices[b].x;
    }

    return result * .5f;
}

The tanda dari hasil (positif atau negatif) akan memberitahu Anda apakah itu searah jarum jam atau berlawanan arah jarum jam. Anda perlu mencoba ini untuk melihat ke arah mana putaran itu bagi Anda karena itu tergantung pada sistem koordinat Anda.

Jika bentuknya searah jarum jam:

  • Makhluk yang maju ke depan bentuknya akan searah jarum jam , dan
  • Makhluk yang mundur bentuknya akan berlawanan arah jarum jam .

Jika bentuknya berlawanan arah jarum jam:

  • Makhluk yang maju ke depan bentuknya akan berlawanan arah jarum jam , dan
  • Makhluk yang mundur bentuknya akan searah jarum jam .
Chris Burt-Brown
sumber
0

Tampaknya Trevor sudah membahas pertanyaan ini, tetapi inilah solusi saya:

  1. hitung luas yang Anda bentuk, artinya

    area = 0
    foreach (edge in shape)
        area += edge.begin.x * edge.end.y - edge.begin.y * edge.end.x
  2. menggunakan area yang dihitung seperti di atas Anda dapat dengan mudah mengetahui apakah bentuk itu sendiri searah jarum jam atau tidak. itu searah jarum jam hanya jika area di bawah nol.

  3. periksa apakah objek bergerak dengan cara yang sama seperti simpul adalah urutan atau dalam arah yang berlawanan.

Ali1S232
sumber