C++で円と長方形の重なりを判定するアルゴリズム

問題の概要

円を (radius, xc, yc) という形式で表します。ここで (xc, yc) は円の中心座標です。同様に、軸に平行な長方形(軸平行境界ボックス)を (x1, y1, x2, y2) という形式で表し、(x1, y1) が左下隅の座標、(x2, y2) が右上隅の座標とします。このとき、円と長方形が互いに重なっているかどうかを判定する必要があります。

たとえば、次のような入力が与えられた場合を考えてみましょう。

この場合、出力は true(重なりあり)となります。

解決のアプローチ

この問題を解く鍵は、「長方形の中で円の中心に最も近い点」を見つけることです。その点と円の中心との距離が半径以下であれば、円と長方形は重なっていると判断できます。具体的には、以下の手順に従います。

• eval() 関数を定義する: 引数 a, b, c を受け取り、max(b, min(a, c)) を返します。これは値を範囲 [b, c] 内にクランプ(制限)する処理です。

• 最寄り点を計算する: cdx := eval(cx, left, right)、cdy := eval(cy, bottom, top) により、長方形内で円の中心に最も近い点の座標を求めます。

• 幅と高さを求める: rwid := right − left、rh := top − bottom。

• 距離を計算する: dx := cx − cdx、dy := cy − cdy とし、二乗距離 disSq := (dx × dx) + (dy × dy) を求めます。

• 半径の二乗を求める: sqrRadius := (r × r)。

• 判定する: disSq ≤ sqrRadius であれば true、そうでなければ false を返します。

なお、平方根を計算せずに距離の二乗と半径の二乗を直接比較することで、浮動小数点演算のコストを抑え、高速かつ正確に判定できます。

C++による実装例

それでは、実際の実装を見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int eval(int a, int b, int c){
        return max(b, min(a, c));
    }
    bool checkOverlap(int r, int cx, int cy, int left, int bottom, int right, int top){
        double cdx = eval(cx, left, right);
        double cdy = eval(cy, bottom, top);
        double rwid = right - left;
        double rh = top - bottom;
        double dx = cx - cdx;
        double dy = cy - cdy;
        double disSq = (dx * dx) + (dy * dy);
        double sqrRadius = (r * r);
        return (disSq <= sqrRadius);
    }
};
main(){
    Solution ob;
    cout << (ob.checkOverlap(1, 0, 0, 1, -1, 3, 1));
}

入力

1, 0, 0, 1, -1, 3, 1

この入力は、「半径 1・中心 (0, 0) の円」と「左下 (1, −1)、右上 (3, 1) の長方形」を表しています。

出力

1

出力の 1 は true、つまり円と長方形が重なっていることを意味します。

計算量について

このアルゴリズムは、クランプ処理と距離計算のみで構成されているため、時間計算量 O(1)、空間計算量 O(1) で動作します。衝突判定や当たり判定が必要なゲーム開発などでも広く使われる、シンプルかつ効率的な手法です。