[解決済み] 2つの矩形の交差を検出するアルゴリズム？

質問

2つの矩形が交差しているかどうかを検出するアルゴリズムを探しています（一方は任意の角度で、他方は垂直/水平の線のみで）。

片方の角がもう片方にあるかどうかのテストは、ほぼうまくいきます。 長方形が十字のような形になると失敗します。

線の勾配を利用すると、縦線に特殊なケースが必要になるので、それを避けるのが良さそうですね。

どのように解決するのですか？

標準的な方法としては 分離軸テスト (でググってみてください）。

要するに

• 2つのオブジェクトは、2つのオブジェクトを分離する線を見つけることができれば、交差しない。例：オブジェクト/オブジェクトのすべての点は、線の異なる側にある。

面白いのは、2つの長方形のすべての辺をチェックするだけで十分なことです。もし矩形が重なっていなければ、どちらかの辺が分離軸になります。

2Dでは、スロープを使わなくてもこのようなことができます。エッジは単に2つの頂点の差として定義されます。

  edge = v(n) - v(n-1)

これを90°回転させると直角が得られます。2Dでは次のように簡単です。

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

つまり、三角法も傾きも関係ないのです。ベクトルを単位長さに正規化することも必要ありません。

ある点が直線の片側にあるか反対側にあるかを調べるには、単に内積を使用すればよい。

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

次に、矩形Aのすべての点を矩形Bのエッジに対してテストしてください。もし分離辺が見つかれば、オブジェクトは交差しません（Bの他のすべての点が、テストされた辺の反対側にあることが条件です。） 分離辺が見つからない場合は、矩形が交差しているか、一方の矩形が他方の矩形に含まれているかのどちらかです。

このテストは、どんな凸多角形でも動作する...。

訂正します。 分離辺を特定するためには、一方の長方形のすべての点を他方の長方形の各辺と照合するだけでは不十分である。候補エッジE（下図）は、Aのすべての点がEの同じ半平面上にあるため、分離エッジとして識別されます。しかし、Bの頂点Vb1、Vb2もその半平面上にあるため、分離エッジではありません。そうでない場合にのみ分離辺となる。 http://www.iassess.com/collision.png