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との最短距離を 、最長距離を としたとき、
「 円Cの半径」かつ「円Cの半径」
を満たすとき、円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