交差するかどうかに関係なく、関数で返さなければならない 2 つの四角形があります。
それらは[ x0, y0, x1, y1 ]、長方形の左上隅と右下隅を表すペアで表されます。あるいは、あなたの解決策は[ x0, y0, width, height ]、それがどういうわけか単純である場合、関数のパラメーター入力をそれによって適応させることができます。
長方形 A の 2 つの角のいずれかが長方形 B に含まれているかどうかを確認しようとしましたが、A が B よりも大きく、B が部分的に A に含まれている場合、重複していないと表示されます。これで A と B を試すことができましたが、これは悪い方法のようです。
大きなグリッドを事前に作成して、長方形でセルを占有することはできません。これは、長方形がどのようなものになるかがわからないためです。私が言えることは、それらが符号なし整数であり、最小値が 0 で、最大値が不明であるということだけです。
四角形が確実に交差していない場合を確認します。これらのケースのいずれにも当てはまらない場合、長方形は交差する必要があります。すなわち:
public boolean rectanglesIntersect(
float minAx, float minAy, float maxAx, float maxAy,
float minBx, float minBy, float maxBx, float maxBy ) {
boolean aLeftOfB = maxAx < minBx;
boolean aRightOfB = minAx > maxBx;
boolean aAboveB = minAy > maxBy;
boolean aBelowB = maxAy < minBy;
return !( aLeftOfB || aRightOfB || aAboveB || aBelowB );
}
これは概念を示していますが、ブール値をインライン化して、の短絡動作を利用することで、わずかに高速化できます。||
しばらくして、2 つの回転した四角形間の衝突の検出に関する完全な回答をやり直すことにしました:回転した四角形が互いに衝突するタイミングを検出する方法
2 つの回転した長方形が衝突するかどうかを確認する場合は、一方の長方形の角をもう一方の軸に投影する必要があります。rectA のすべての射影が rectB に当たり、rectB の射影が rectA に当たると、2 つの長方形が衝突します。
一部の投影はここでは衝突しません。2 つの長方形は衝突しません。
4 つの投影が他の長方形に当たり、2 つの長方形が衝突します。
理解を深めるために、このJSFiddleに関するプレゼンテーションを行いました。
is_collideより多くの例について関数を確認できます
問題（アルゴリズム）を反対側から見ると、ケースは非常に単純であることがわかります。
つまり、「長方形は重なっていますか?」という質問に答える代わりに、「長方形は重なっていませんか?」という質問に答えます。
結局、両方の質問は同じ問題を解決しますが、2 番目の質問への答えは実装が簡単です。これは、一方が他方の下にある場合、または一方が他方の左側にある場合にのみ長方形が重ならないためです (一方の質問で十分です)。もちろん、両方が同時に発生することもあります。ここでは、論理条件「または」をよく理解することが重要です)。これにより、最初の質問で考慮する必要がある多くのケースが減少します。
適切な変数名を使用することで、全体の問題も簡素化されます。
const areRectanglesOverlap = (rect1, rect2) => {
let [left1, top1, right1, bottom1] = [rect1[0], rect1[1], rect1[2], rect1[3]],
[left2, top2, right2, bottom2] = [rect2[0], rect2[1], rect2[2], rect2[3]];
// The first rectangle is under the second or vice versa
if (top1 < bottom2 || top2 < bottom1) {
return false;
}
// The first rectangle is to the left of the second or vice versa
if (right1 < left2 || right2 < left1) {
return false;
}
// Rectangles overlap
return true;
}
四角形の表現が異なる場合でも、変数の変更が定義されているセクションのみを変更することで、上記の関数をそれに適応させるのは簡単です。関数の残りの部分は変更されていません (もちろん、ここではコメントは必要ありませんが、この単純なアルゴリズムを誰もがすぐに理解できるようにコメントを追加しました)。
上記の関数と同等ですが、おそらく少し読みにくい形式は次のようになります。
const areRectanglesOverlap = (rect1, rect2) => {
let [left1, top1, right1, bottom1] = [...rect1],
[left2, top2, right2, bottom2] = [...rect2];
return !(top1 < bottom2 || top2 < bottom1 || right1 < left2 || right2 < left1);
}
点 UL1 と LR1 を持つ長方形 1 と、点 UR2 と LR2 を持つ長方形 2 を指定します -
UL1 が r2 にあるか、LR1 が r2 にあるかを確認します (図のケース 1 とケース 2)。最後に、UR2 / LR2 のいずれかが r1 にあるかどうかを確認します (図のケース 3)。
x と y が四角形の x と y の範囲の最小値と最大値の間にあることを確認することで、点が四角形内にあるかどうかを確認します。
クリア？
青がR1、紫がR2
x 領域と y 領域の両方が重なっている場合、2 つの四角形が重なっています。x 座標のいずれかが他の四角形と重なっている場合は、重なりがあります。
x 軸に沿って、最初の点が他の 2 つの長方形内にあるか、2 番目の点が他の 2 つの長方形内にあるか、または 2 つの点が他の点の反対側にあります。
function checkRectOverlap(rect1, rect2) {
/*
* Each array in parameter is one rectangle
* in each array, there is an array showing the co-ordinates of two opposite corners of the rectangle
* Example:
* [[x1, y1], [x2, y2]], [[x3, y3], [x4, y4]]
*/
//Check whether there is an x overlap
if ((rect1[0][0] < rect2[0][0] && rect2[0][0] < rect1[1][0]) //Event that x3 is inbetween x1 and x2
|| (rect1[0][0] < rect2[1][0] && rect2[1][0] < rect1[1][0]) //Event that x4 is inbetween x1 and x2
|| (rect2[0][0] < rect1[0][0] && rect1[1][0] < rect2[1][0])) { //Event that x1 and x2 are inbetween x3 and x4
//Check whether there is a y overlap using the same procedure
if ((rect1[0][1] < rect2[0][1] && rect2[0][1] < rect1[1][1]) //Event that y3 is between y1 and y2
|| (rect1[0][1] < rect2[1][1] && rect2[1][1] < rect1[1][1]) //Event that y4 is between y1 and y2
|| (rect2[0][1] < rect1[0][1] && rect1[1][1] < rect2[1][1])) { //Event that y1 and y2 are between y3 and y4
return true;
}
}
return false;
}