Wikipediaや既存の記事でも解説していただいていますが、これをもう少し高速化する事を考えます。
→当たり判定のアルゴリズム（2D 四角×四角）
前準備
$x_1 < x_2,y_1 < y_2$を満たす矩形の対角線上の２点$(x_1,y_1),(x_2,y_2)$が取得できる状態とします。
(以降、この２点を矩形の『代表点』と呼称することにします)
数学とかで見かけるような座標系(＝紙面・画面に対して$x$軸が右方向、$y$軸が上方向に正となる座標系)では、矩形の左下及び右上の点が取得できる状態とします。
判定式
下図に示したような、矩形$A,B$それぞれの代表点$(x_{a1},y_{a1}),(x_{a2},y_{a2}),(x_{b1},y_{b1}),(x_{b2},y_{b2})$について、次の論理式が成り立つ場合は、$A,B$が衝突していない事を示しています。
\left(x_{a2}<x_{b1}\right)\vee\left(x_{b2}<x_{a1}\right)\vee\left(y_{a2}<y_{b1}\right)\vee\left(y_{b2}<y_{a1}\right)
※念のために、$\vee$は論理和を表します。
例えば、矩形$A$が$(0,0),(5,5)$、矩形$B$が$(1,1),(6,4)$の場合では、
(5<0)\vee(6<1)\vee(5<1)\vee(4<0)=F \vee F \vee F \vee F=Fとなり、矩形$A,B$が衝突している事になります。
(実際に作図すると、$A$の辺と$B$が交差するような配置になるかと思います)
境界での挙動
示した論理式では矩形の辺が隣接した場合も衝突すると判定されます。上記論理式の不等号$<$を$\leqq$に置き換えてあげると、辺が隣接していても衝突していないと判定できます。
なぜこれで判別できるのか？
ちゃんとした証明は後でやってみたいと思いますが、基本方針としては、最初に定義した代表点の取り方から、衝突しないときの各代表点の$x,y$成分についての大小関係を使います。
まず、矩形$A,B$が衝突しないときは、代表点の各成分について次の事が成り立っています。
\begin{eqnarray}
x成分&:&(x_{a1} < x_{a2} < x_{b1} < x_{b2}) &\vee& (x_{b1} < x_{b2} < x_{a1} < x_{a2})\
y成分&:&(y_{a1} < y_{a2} < y_{b1} < y_{b2}) &\vee& (y_{b1} < y_{b2} < y_{a1} < y_{a2})
\end{eqnarray}
また、矩形が衝突しないときは、ある成分同士で見たときに衝突していない場合が存在するときなので、上に示した不等式のうちどれかが満たされるならば矩形は衝突していないと判定できます。よって、次の式に変形できます。 ```math
\begin{eqnarray}
(x_{a1} < x_{a2} < x_{b1} < x_{b2}) &\vee& (x_{b1} < x_{b2} < x_{a1} < x_{a2})\
\ \ &\vee&(y_{a1} < y_{a2} < y_{b1} < y_{b2})\
\ \ &\vee&(y_{b1} < y_{b2} < y_{a1} < y_{a2})
\end{eqnarray}
ここで、各矩形の代表点の取り方より次の式が自明です。 ```math
(x_{a1} < x_{a2}),\ \ (x_{b1} < x_{b2}),\ \ (y_{a1} < y_{a2}),\ \ (y_{b1} < y_{b2})
結果的に、次のような式が成り立つならば、衝突していないと判定できます。 ```math
\left(x_{a2}<x_{b1}\right)\vee\left(x_{b2}<x_{a1}\right)\vee\left(y_{a2}<y_{b1}\right)\vee\left(y_{b2}<y_{a1}\right)
C++によるサンプルコード
以下に、C++で実装したサンプルコードを示します。
衝突していないときはno collision、衝突しているときはcollisionと標準出力します。
#include <iostream>
using namespace std;
typedef struct _pos {
double x; // X-axis
double y; // Y-axis
}pos;
int main() {
pos a1, a2, b1, b2;
cout << "RectA: ";
cin >> a1.x >> a1.y >> a2.x >> a2.y;
cout << "RectB: ";
cin >> b1.x >> b1.y >> b2.x >> b2.y;
if(a2.x < b1.x || b2.x < a1.x || a2.y < b1.y || b2.y < a1.y)
cout << "no collision" << endl; // 衝突していないと判定
else
cout << "collision" << endl; // 衝突していると判定
return 0;
}
元ネタとの比較
元ネタでは矩形の中心座標や辺の長さを取得するために絶対値の取得や除算を使っていましたが、こちらは各代表点との大小比較だけで判別可能なので、元ネタよりも計算速度が改善できると思います。
(ただし、昨今のコンピュータの性能を考えると微々たるものかとは思いますが…)
3Dへの応用
同じような手法で、直方体の衝突判定も大小判定のみでできると思いますが、比較する値は多くなると思います。(おそらく、$x,y,z$各成分3回、合計9回の大小判定でできる？)
あとがき
3年ぶりにAizu Online Judgeの問題『Problem 0029 - Intersection of Rectangles』を解いたときにふっと思いついたアルゴリズムでしたが、実際にACをもらう事が出来たので執筆しました。(ついでに初めて書いたQiitaの記事となります...///)
あまり大したアルゴリズムではありませんが、今後競プロをしていく方の一助になれば幸いです。
おまけ
私のブラウザ(Vivaldi)でこの記事を見直してみたときに、数式の部分にスクロールバーがついて表示が崩れているのですが、同じような人いませんか...？