四角形内に円が内包する判定するプログラム

四角形内に縁が内包しているか判定するプログラムについてまとめたいと思います。

題材にするのは、AIZU ONINE JUDGEのCircle In Rectangleという問題です。

四角形内に円が内包するか判定する例題

長方形の中に円が含まれるかを判定するプログラムを作成してください。
次のように、長方形は左下の頂点を原点とし、右上の頂点の座標 (W,H) が与えられます。
また、円はその中心の座標 (x,y) と半径 r で与えられます。

入力

５つの整数 W、H、x、y、r が空白区切りで１行に与えられます。

出力

円が長方形の内部に含まれるなら Yes と、一部でもはみ出るならば No と１行に出力してください。

四角形内に円が内包する条件

下図より、四角形を形成する各々の直線と、円が交差(はみ出している場合)は円は内包されていません。

また、下図のように、四角形を形成する直線と円が交差してなくとも、円の中心が四角形内にない場合は、円に内包されていません。

これらの条件を組み合わせれば、四角形に円が内包されているか判定することができそうです。

円が四角形を形成する各々の線分と衝突しているか判定する方法

円の中心と直線との距離dを算出して、dと半径を比較して、半径よりもdが短かった場合に、
円と直線が衝突していると判定できます。

点と直線の距離については、こちらにまとめました。

円の中心が四角形に存在するか判定する方法

四角形が原点(0,0),width,heightのみを与えれているので、
点がwidth,heightの範囲内か判定すればokです。

点と直線の距離の公式をプログラムで表す

以下のように点と直線の距離を返す関数を定義しました。

struct Vec2{
    int x;
    int y;
    
    Vec2(int x1,int y1){
        x = x1;
        y = y1;
    }
    Vec2(){
        
    }
};

float getlengthLineBetweenPoint(float a,float b,float c,Vec2 point){
    // 点と直線の距離の公式に当てはめる
    return abs((a * point.x + b * point.y + c) / sqrt((a * a) + (b * b)));
}

全体のコード

問題の答えとなるコードは以下のように書きました。

#include <iostream>
#include <stdlib.h>
#include <math.h>

using namespace std;

struct Vec2{
    int x;
    int y;
    
    Vec2(int x1,int y1){
        x = x1;
        y = y1;
    }
    Vec2(){
        
    }
};

struct Line{
    // vector2D
    Vec2 base;
    // vector2D
    Vec2 direction;
};

float getlengthLineBetweenPoint(float a,float b,float c,Vec2 point){
    // 点と直線の距離の公式に当てはめる
    return abs((a * point.x + b * point.y + c) / sqrt((a * a) + (b * b)));
}

int main(void){
    int width,height,centerX,centerY,radius;
    cin >> width >> height >> centerX >> centerY >> radius;
    
    // 原点を通る縦直線(x = 0)
    float distance1 = getlengthLineBetweenPoint(1,0,0,Vec2(centerX,centerY));
    // 原点を通る横直線(y = 0)
    float distance2 = getlengthLineBetweenPoint(0,1,0,Vec2(centerX,centerY));
    // 縦直線
    float distance3 = getlengthLineBetweenPoint(1,0,-width,Vec2(centerX,centerY));
    // 横直線
    float distance4 = getlengthLineBetweenPoint(0,1,-height,Vec2(centerX,centerY));
    
    string str = "No";
    // 円の半径の距離が全ての直線との距離未満ならばぶつかっていないことになる
    // 円と直線がぶつかっていない
    if(distance1 >= radius && distance2 >= radius && distance3 >= radius && distance4 >= radius){
        // かつ円の中心が四角形の内部になる
        // x座標
        if(centerX > 0 && centerX < width){
            // y座標
            if(centerY > 0 && centerY < height){
                str = "Yes";
            }
        }
    }
    cout << str << endl;
    
    return 0;
}

まとめ

四角形に円が内包するかの条件は、
1.円と各々の直線が交差しているか
2.四角形内に円の中心が内包しているか

で判定することができる。

効率の良いやり方は、いくらでもあると思うけど。
単純でできそうなやり方をいくつか考えたけれど、一般的な方法で落ち着いてしまった。。。