1. ホーム
  2. geometry

[解決済み】円・矩形の衝突判定(交差判定)について)

2022-04-16 20:02:53

質問

2次元ユークリッド空間において、円と長方形が交差しているかどうかを判断するにはどうしたらよいでしょうか?(すなわち、古典的な2次元幾何学)

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

円が矩形と交差するケースは2つしかない。

  • 円の中心が長方形の内側にある、または
  • 長方形の辺の1つが円内の点を持つ。

なお、この場合、長方形は軸と平行である必要はない。

(一つの見方として、どの辺も円の中に点がない場合(すべての辺が完全に円の外にある場合)、円が多角形と交差できる唯一の方法は、円が完全に多角形の中にある場合です)。

このように考えると、次のようなものがうまくいくでしょう。 P と半径 R で、矩形の頂点は A , B , C , D の順で表示されます(完全なコードではありません)。

def intersect(Circle(P, R), Rectangle(A, B, C, D)):
    S = Circle(P, R)
    return (pointInRectangle(P, Rectangle(A, B, C, D)) or
            intersectCircle(S, (A, B)) or
            intersectCircle(S, (B, C)) or
            intersectCircle(S, (C, D)) or
            intersectCircle(S, (D, A)))

もしあなたが何かジオメトリを書いているのなら、上記の関数はすでにあなたのライブラリにあることでしょう。そうでない場合は pointInRectangle() は、いくつかの方法で実装することができます。 ポリゴン内の点 メソッドが動作しますが、矩形の場合は、これが動作するかどうかを確認するだけです。

0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD

そして intersectCircle() からの垂線の足が、このような場合にも簡単に実装することができます。 P が十分に近く、かつ端点と端点の間にあることを確認し、そうでない場合は端点をチェックします。

クールなのは 同じ のアイデアは、矩形だけでなく、円形と任意の 単純多角形 - は、凸である必要はありません。