足跡-sokuseki-

りかの日進月歩の記録

C++のcomplexで円と線分の交差判定

ある円Cと線分Sの交差判定をします。

定義

円と線分(ここでは直線として管理します)の定義は↓

typedef complex<double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
  L(){;}
};

struct C {
  P c;double r;
  C(const P &c,double r):c(c),r(r){}
  C(){;}
};

実装

基本的な考え方は、円の中心と線分との距離を見ます。
円Cの中心と線分Sとの最短距離を  d_{min} 、最長距離を  d_{max} としたとき、
 d_{min} \le 円Cの半径」かつ「円Cの半径 \le d_{max}
を満たすとき、円Cと線分Sは交差します。

以下のコードでは、円と線分の交差判定をintersectCS()、線分と点の距離をdistanceSP()、点と点の距離をdistancePP()で計算しています。(intersectCS()以外は省略)

bool intersectCS(const C &c, const L &l){//円と線分の交差判定
    double close = distanceSP(l,c.c);
    double far = max(distancePP(l[0],c.c),distancePP(l[1],c.c));
    if(close <= c.r && far >= c.r)return true; //重なっていても良い
    //完全に交差している場合のみだと、イコールを外す
    return false;
}

verifyと全体コード

verifyはAOJ0129で行いました。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129
提出したコード:
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4060205