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

Katakanlah kita memiliki bentuk bergerigi:

Dan dua makhluk bergerak di sepanjang garis besarnya.

Lalu kami menghaluskan bentuk sepenuhnya dengan menarik sudut keluar.

Kami mendapatkan ini:

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

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.

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

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.

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.

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 .

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.