先に結論を書きます。 円を中心が (x, y) 半径 r で軸並行矩形の中心が (cx, cy) 横幅が w 縦幅が h とすると、
bool HitTestCircle2AABB(float x, float y, float r, float cx, float cy, float h, float w) { float dx = std::max(0.f, std::abs(x - cx) - w); float dy = std::max(0.f, std::abs(y - cy) - h); return dx * dx + dy * dy <= r * r; }
導出
アイデア1
赤の長方形+青の長方形+緑の円4つで判定する
尤も単純な方法。円の個数が多いので効率が悪い。 図形の左右及び上下の対称性に注目して効率化を図る。 絶対値をとることで右上のみに限定させると以下が得られる。
アイデア1 (改良ver)
これで赤い長方形+青い長方形+緑の円1つになった。
アイデア1はこれ以上改良できない(たぶん...)
では、アイデア2を紹介する。
アイデア2
円の中心から 最も近い軸並行矩形の外周との距離を求めて、半径以内ならOK。とする。
この最近傍点からの距離って求めるのが難しそうな気がしたんですけど（僕だけ？凸射影みたいなのって大変そうなイメージがった）流石に図形が単純なので、最近傍点やそこへの距離は簡単に求まります。
例えば x軸での最近傍点までの距離 dx は
max(max(0, x - (cx + w)), max(0, -x + (cx - w)));
で求まります。 dyも同様に計算して、 dx2+dy2<=r2の判定だけで終わります。
アイデア2 (改良)
maxは可換で結合則も満たす(可換半群)ので順番を入れ替えて
float dx = max(0, max(x - (cx + w), -x + (cx - w)));
max(x - (cx + w), -x + (cx - w)) という部分は加減算が4回あるわけですが、第一引数と第二引数の符号の不変部分と反転部分に分けると
(x - cx) は反転して、-w は不変であることがわかります。
よって、
float hoge = x - cx; float dx = max(0, max(hoge - w, -hoge - w));
とすれば加減算を1回減らせますね。
さらに、max(z1 + w, z2 + w) == max(z1, z2) + w より
float hoge = x - cx; float dx = max(0, max(hoge, -hoge) - w);
までできます。
max(z1, -z1) == abs(z1) より、
float dx = max(0, abs(x-cx)-w)
までできました！もちろんこれはアイデア1の改良と同じく対称性を利用しただけなので最初からこれ思いついとけよって話ですね。何を長々と解説してるんだという話ですが、言い訳をさせてください。 最初私は min(max(0, ...), max(0, ...)) だと思い込んでいて、その場合の式変形はこのプロセスを通らないとかなり難しいです。そして意気揚々とこの記事を書いたところ、max(max(0, ...), max(0, ...))であることに気付いて全部修正した結果、こんな駄文を書き連ねることになってしまいました。かなしいね。 最後まで読んでいただきありがとうございます。
おまけというか、軸並行矩形(AABB)の実現の2種類についてちょっと触れておきます。 AABBを中心と幅で持つ方法と、対角線上の2点の座標(右上と左下)をもつ方法があると思います。 前者はオブジェクトが頻繁に動く際、中心位置のみの更新なので楽です。 後者の場合、直感的にオブジェクトを配置することができますが、移動がある場合2点とも更新なので面倒です。 当たり判定処理に関してはほぼ変わりません。 個人的には中心と幅を持つ方がいいかなと思います。
