Saya mencoba untuk menulis program C ++ yang mengambil input berikut dari pengguna untuk membangun persegi panjang (antara 2 dan 5): tinggi, lebar, x-pos, y-pos. Semua persegi panjang ini akan ada sejajar dengan sumbu x dan sumbu y, yaitu semua tepinya memiliki kemiringan 0 atau tak hingga.
Saya sudah mencoba menerapkan apa yang disebutkan dalam pertanyaan ini tetapi saya tidak memiliki banyak keberuntungan.
Implementasi saya saat ini melakukan hal berikut:
// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2
// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2];
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];
int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;
Namun saya tidak begitu yakin apakah (a) saya telah mengimplementasikan algoritma yang saya tautkan dengan benar, atau jika saya benar-benar bagaimana mengartikannya?
Ada saran?
Jawaban:
atau, menggunakan koordinat Cartesian
(Dengan X1 yang kiri coord, X2 menjadi kanan coord, meningkat dari kiri ke kanan dan Y1 menjadi coord Atas, dan Y2 menjadi coord Bawah, meningkat dari bawah ke atas - jika ini bukan bagaimana sistem koordinat Anda [misalnya kebanyakan komputer memiliki Arah Y terbalik], tukar perbandingan di bawah ) ...
Katakanlah Anda memiliki Rect A, dan Rect B. Proof adalah dengan kontradiksi. Salah satu dari empat ketentuan ini menjamin bahwa tidak ada tumpang tindih yang dapat terjadi :
Jadi syarat untuk Non-Overlap adalah
Oleh karena itu, kondisi yang cukup untuk Tumpang tindih adalah sebaliknya.
Hukum De Morgan mengatakan
Not (A or B or C or D)
sama denganNot A And Not B And Not C And Not D
menggunakan De Morgan, yang kita miliki
Ini setara dengan:
RectA.Left < RectB.Right
], danRectA.Right > RectB.Left
], danRectA.Top > RectB.Bottom
], danRectA.Bottom < RectB.Top
]Catatan 1 : Cukup jelas prinsip yang sama ini dapat diperluas ke sejumlah dimensi.
Catatan 2 : Seharusnya juga cukup jelas untuk menghitung tumpang tindih hanya satu piksel, mengubah batas
<
dan / atau>
pada batas itu menjadi a<=
atau a>=
.Catatan 3 : Jawaban ini, ketika menggunakan koordinat Cartesian (X, Y) didasarkan pada koordinat Cartesian aljabar standar (x meningkat dari kiri ke kanan, dan Y naik dari bawah ke atas). Jelas, di mana sistem komputer dapat memekanisasi koordinat layar secara berbeda, (mis., Meningkatkan Y dari atas ke bawah, atau X Dari kanan ke kiri), sintaks perlu disesuaikan sesuai /
sumber
sumber
B.height
seharusnyaA.height
#undef min
dan#undef max
, atau dengan menggunakan nama parameter yang berbeda.#define BETWEEN(value,min,max) \ (\ value > max ? max : ( value < min ? min : value )\ )
xOverlap
adalah dalam satu dimensi;rectOverlap
adalah dua dimensi. Itu dapat diperluas ke dimensi N menggunakan loop.sumber
Lebih mudah untuk memeriksa apakah persegi panjang lengkap di luar yang lain, jadi jika itu baik
di kiri...
atau di sebelah kanan ...
atau di atas ...
atau di bawah ...
dari persegi panjang kedua, itu tidak mungkin berbenturan dengannya. Jadi untuk memiliki fungsi yang mengembalikan Boolean mengatakan cuaca persegi panjang bertabrakan, kita cukup menggabungkan kondisi dengan OR logis dan meniadakan hasilnya:
Untuk sudah menerima hasil positif saat hanya menyentuh, kita dapat mengubah "<" dan ">" dengan "<=" dan "> =".
sumber
Tanyakan kepada diri Anda pertanyaan yang berlawanan: Bagaimana saya bisa menentukan apakah dua persegi panjang tidak berpotongan sama sekali? Jelas, persegi panjang A sepenuhnya di sebelah kiri persegi panjang B tidak berpotongan. Juga jika A sepenuhnya ke kanan. Dan juga jika A benar-benar di atas B atau sepenuhnya di bawah B. Dalam kasus lain, A dan B berpotongan.
Yang berikut mungkin memiliki bug, tetapi saya cukup yakin tentang algoritme:
sumber
Misalkan Anda telah menentukan posisi dan ukuran persegi panjang seperti ini:
Implementasi C ++ saya seperti ini:
Contoh panggilan fungsi sesuai dengan gambar yang diberikan di atas:
Perbandingan di dalam
if
blok akan terlihat seperti di bawah ini:sumber
Begini cara melakukannya di API Java:
sumber
Dalam pertanyaan, Anda menautkan ke matematika kapan persegi panjang berada pada sudut rotasi yang sewenang-wenang. Jika saya mengerti sedikit tentang sudut dalam pertanyaan, saya menafsirkan bahwa semua persegi panjang saling tegak lurus.
Seorang ahli yang mengetahui bidang formula yang tumpang tindih adalah:
Menggunakan contoh:
1) kumpulkan semua koordinat x (kiri dan kanan) ke dalam daftar, kemudian urutkan dan hapus duplikatnya
2) kumpulkan semua koordinat y (baik atas dan bawah) ke dalam daftar, lalu urutkan dan hapus duplikatnya
3) membuat array 2D dengan jumlah kesenjangan antara koordinat x unik * jumlah kesenjangan antara koordinat y unik.
4) cat semua persegi panjang ke dalam kisi ini, menambah jumlah setiap sel yang terjadi pada:
5) Saat Anda melukis persegi panjang, mudah untuk mencegat tumpang tindih.
sumber
sumber
Jangan menganggap koordinat sebagai menunjukkan di mana piksel berada. Anggap mereka berada di antara piksel. Dengan begitu, luas persegi panjang 2x2 harus 4, bukan 9.
sumber
Cara termudah adalah
pertama-tama taruh dalam pikiran Anda bahwa di komputer sistem koordinat terbalik. Sumbu x sama dengan matematika tetapi sumbu y meningkat ke bawah dan berkurang jika naik ke atas .. jika persegi panjang diambil dari pusat. jika koordinat x1 lebih besar dari x2 ditambah bagian lebarnya. maka itu berarti setengah mereka akan saling menyentuh. dan dengan cara yang sama turun + setengah dari ketinggiannya. itu akan bertabrakan ..
sumber
Katakanlah dua persegi panjang adalah persegi panjang A dan persegi panjang B. Biarkan pusatnya menjadi A1 dan B1 (koordinat A1 dan B1 dapat dengan mudah ditemukan), biarkan ketinggiannya menjadi Ha dan Hb, lebar menjadi Wa dan Wb, biarkan dx menjadi lebar (x) jarak antara A1 dan B1 dan dy menjadi tinggi (y) jarak antara A1 dan B1.
Sekarang kita dapat mengatakan kita dapat mengatakan A dan B tumpang tindih: kapan
sumber
Saya telah mengimplementasikan versi C #, mudah dikonversi ke C ++.
sumber
Saya punya solusi yang sangat mudah
biarkan x1, y1 x2, y2, l1, b1, l2, menjadi kordinat dan panjang dan luasnya masing-masing
pertimbangkan kondisinya ((x2
sekarang satu-satunya cara persegi panjang ini akan tumpang tindih adalah jika titik diagonal ke x1, y1 akan terletak di dalam persegi panjang lain atau sama dengan titik diagonal ke x2, y2 akan terletak di dalam persegi panjang lainnya. yang persis menyiratkan kondisi di atas.
sumber
A dan B menjadi dua persegi panjang. C menjadi persegi panjang penutup mereka.
Itu menangani semua kasus yang mungkin.
sumber
Ini dari latihan 3.28 dari buku Pengantar Java Programming- Comprehensive Edition. Kode menguji apakah kedua persegi panjang adalah indenticle, apakah satu berada di dalam yang lain dan apakah satu berada di luar yang lain. Jika tidak satu pun dari kondisi ini terpenuhi maka keduanya tumpang tindih.
** 3.28 (Geometri: dua persegi panjang) Tulis program yang meminta pengguna untuk memasukkan pusat x-, koordinat y, lebar, dan tinggi dua persegi panjang dan menentukan apakah persegi panjang kedua berada di dalam yang pertama atau tumpang tindih dengan yang pertama, seperti yang ditunjukkan pada Gambar 3.9. Uji program Anda untuk mencakup semua kasus. Berikut ini contoh proses:
Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 2.5 4 2.5 43 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 1.5 5 0.5 3 r2 ada di dalam r1
Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 1 2 3 5.5 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 3 4 4,5 5 r2 tumpang tindih r1
Masukkan pusat x, koordinat y, lebar, dan tinggi r1: 1 2 3 3 Masukkan pusat x, koordinat y, lebar, dan tinggi r2: 40 45 3 2 r2 tidak tumpang tindih dengan r1
sumber
sumber
Bagi Anda yang menggunakan titik pusat dan setengah ukuran untuk data persegi panjang mereka, alih-alih khas x, y, w, h, atau x0, y0, x1, x1, berikut ini cara melakukannya:
sumber
sumber
Jika persegi panjang tumpang tindih maka area tumpang tindih akan lebih besar dari nol. Sekarang mari kita temukan area yang tumpang tindih:
Jika mereka tumpang tindih maka tepi kiri overlap-rect akan menjadi
max(r1.x1, r2.x1)
dan tepi kanan akanmin(r1.x2, r2.x2)
. Jadi panjang tumpang tindihnya adalahmin(r1.x2, r2.x2) - max(r1.x1, r2.x1)
Jadi area akan menjadi:
Jika
area = 0
kemudian mereka tidak tumpang tindih.Sederhana bukan?
sumber
"Jika Anda melakukan pengurangan x atau y koordinat yang sesuai dengan simpul dari dua yang menghadap setiap persegi panjang, jika hasilnya adalah tanda yang sama, kedua persegi panjang tidak tumpang tindih dengan sumbu itu" (maaf, saya tidak yakin terjemahan saya benar. )
Sumber: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html
sumber
Kode Java untuk mencari tahu apakah Rectangles saling kontak atau tumpang tindih
...
...
sumber