Menemukan arah perjalanan di dunia dengan tepi terbungkus

Saya perlu menemukan arah jarak terpendek dari satu titik di dunia 2D saya ke titik lain di mana ujung-ujungnya dibungkus (seperti asteroid dll). Saya tahu cara menemukan jarak terpendek tetapi saya berjuang untuk menemukan arahnya.

Jarak terpendek diberikan oleh:

int rows = MapY;
int cols = MapX;

int d1 = abs(S.Y - T.Y);
int d2 = abs(S.X - T.X);
int dr = min(d1, rows-d1);
int dc = min(d2, cols-d2);

double dist = sqrt((double)(dr*dr + dc*dc));

Contoh dunia

                   :         
                   :  T    
                   :         
    :--------------:---------
    :              :
    :           S  :
    :              :
    :              :
    :  T           :
    :              :
    :--------------:

Dalam diagram, tepi ditunjukkan dengan: dan -. Saya telah menunjukkan pengulangan dunia yang dibungkus di kanan atas juga. Saya ingin menemukan arah dalam derajat dari S ke T. Jadi jarak terpendek adalah ke pengulangan kanan atas dari T. tetapi bagaimana saya menghitung arah dalam degreed dari S ke T yang berulang di kanan atas?

Saya tahu posisi S dan T tetapi saya kira saya perlu menemukan posisi T berulang tetapi ada lebih dari 1.

Sistem koordinat dunia dimulai pada 0,0 di kiri atas dan 0 derajat untuk arah bisa dimulai di Barat.

Sepertinya ini seharusnya tidak terlalu sulit tetapi saya belum dapat menemukan solusi. Saya harap ada yang bisa membantu? Setiap situs web akan dihargai.

Anda harus mengubah sedikit algoritme Anda untuk menghitung sudut - saat ini Anda hanya merekam perbedaan absolut dalam posisi, tetapi Anda memerlukan perbedaan relatif (yaitu dapat positif atau negatif tergantung pada penentuan posisi).

int dx = T.X - S.X; // difference in position
int dy = T.Y - S.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - MapX) * -1; // reduce distance by map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + MapX) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (dy - MapY) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY) * -1;

double dist = sqrt(dy*dy+dx*dx); // same as before
double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

Di dunia seperti itu ada jumlah tak terbatas dari S ke T. Mari kita tunjukkan koordinat T by (Tx, Ty), koordinat S by (Sx, Sy), dan ukuran dunia oleh (Wx, Wy). Koordinat terbungkus T adalah (Tx + i * Wx, Ty + j * Wy), di mana idan jadalah bilangan bulat, yaitu elemen dari himpunan {..., -2, -1, 0, 1, 2, ...}. Vektor yang menghubungkan S ke T adalah (Dx, Dy) := (Tx + i * Wx - Sx, Ty + j * Wy - Sy). Untuk (i, j)pasangan tertentu , jarak adalah panjang vektor sqrt(Dx * Dx + Dy * Dy), dan arah dalam radian adalah atan(Dy / Dx). Jalur terpendek adalah salah satu dari 9 jalur, di mana idan jberada di {-1, 0, 1}:

Nilai idan juntuk jalur terpendek dapat ditentukan secara langsung:

int i = Sx - Tx > Wx / 2 ? 1 : Sx - Tx < -Wx / 2 ? -1 : 0;
int j = Sy - Ty > Wy / 2 ? 1 : Sy - Ty < -Wy / 2 ? -1 : 0;

Terima kasih, @IlmariKaronen, @SamHocevar dan @romkyns atas bantuan Anda!

Hitung satu vektor arah yang mungkin, bahkan jika itu bukan yang terpendek, kemudian bungkus koordinat X-nya sehingga berada dalam [-MapX/2,MapX/2]kisaran, dan sama untuk Y:

int DirX = (T.X - S.X + 3 * MapX / 2) % MapX) - MapX / 2;
int DirY = (T.Y - S.Y + 3 * MapY / 2) % MapY) - MapY / 2;

Itu dia! Anda juga mendapatkan jarak tanpa perhitungan lebih lanjut:

double dist = sqrt((double)(DirX*DirX + DirY*DirY));

Saya kira ada beberapa cara untuk melakukan ini. Inilah 2 yang bisa saya pikirkan di atas kepala saya:

# 1: Menangani kasing secara manual

Tepatnya ada 10 kasus yang bisa terjadi:

• Ada di ubin yang sama dengan S
• Ada di salah satu dari 8 ubin sekitarnya
• Tidak ditemukan sama sekali.

Untuk setiap ubin di sekitarnya, mereka adalah permutasi dari perhitungan yang berbeda untuk komponen jarak X atau Y. Karena ini adalah jumlah kasus yang terbatas, Anda bisa membuat hard-code bagaimana menghitungnya, dan menemukan jarak terpendek di antara semuanya.

Berikut ilustrasi 2 kasus untuk ditemukan dx. Kasus 1, di mana Tberada di ubin yang sama dengan S, dx adil S.x - T.x. Untuk ubin di sebelah kanan, dxakan dihitung sebagai TileWidth - S.x + T.x.

               :         
               :  T    
               :         
:--------------:---------
:              :
:           S  :
:  |--------|--:--|
:dx=(S.x-T.x) dx=(TileWidth-S.x+T.x)
:  T           :
:              :
:--------------:

Sebagai optimasi kecil, cari jarak minimum sebelum Anda mengambil akar kuadrat. Kemudian Anda menghemat hingga 7 sqrtpanggilan.

# 2: Abstrak koordinat

Jika Anda perlu melakukan sesuatu yang lebih "cair" secara spasial, seperti algoritme pencarian jalur, abaikan saja koordinatnya sehingga algoritme pencarian jalur Anda bahkan tidak menyadari bahwa dunia terbuat dari ubin berulang. Algoritma path-finding dapat menuju arah yang tidak terbatas secara teoritis (ok well Anda akan dibatasi oleh batas numerik, tetapi Anda mendapatkan intinya).

Untuk perhitungan jarak yang sederhana, jangan repot-repot melakukan ini.

Jangan repot-repot dengan "9 arah". Alasannya adalah bahwa ada 5 kasus yang memburuk di antara mereka 9: "lurus ke utara", "lurus ke barat", "lurus ke selatan", "lurus ke timur" dan "identik". Sebagai contoh, lurus ke utara mengalami kemunduran karena itu merupakan kasus di mana barat laut dan timur laut bergabung dan menghasilkan hasil yang sama.

Dengan demikian, Anda memiliki 4 arah untuk menghitung, dan hanya dapat memilih minimum.

Terima kasih atas semua jawaban pada akhirnya saya menggunakan Toomai yang diedit oleh Scott Chamberlain. Saya juga telah membuat beberapa perubahan karena fakta bahwa sistem koordinat saya mulai dengan y di kiri atas dan meningkat ketika Anda bergerak ke bawah (pada dasarnya terbalik dibandingkan dengan koordinat grafik normal untuk y).

Saya telah memposting kalau-kalau ada orang lain yang menemukan halaman ini dan memiliki sistem y terbalik yang sama.

  int dx = T.X - S.X; // difference in position
int dy = S.Y - T.Y;

if (dx > MapX / 2) // if distance is bigger than half map width, then looping must be closer
    dx = (dx - (MapX / 2)) * -1; // reduce distance by half map width, reverse 
else if (dx < -MapX / 2) // handle the case that dx is negative
    dx = (dx + (MapX / 2)) * -1;

//Do the same for dy
if (dy > MapY / 2)
    dy = (MapY - dy)) * -1;
else if (dy < -MapY / 2)
    dy = (dy + MapY);

double angle = atan2(dy,dx) * 180 / PI; // provides angle in degrees

angle = 180 - angle; //convert to 360 deg