涼雅さんの
この日記に触発されたので作ってみました。
偶然3ヶ月程前に筋道を立てていたので、あとはこれをプログラムにするだけじゃん楽勝ｗｗｗｗとか思っていたのですが、線分や法線を司るクラスを作ったのが半年以上前で、仕様がめちゃくちゃだったのでそこから作り直しましたｗ
とりあえず、筋道はこうです…と説明に入る前に、定義を確認しておきます。
涼雅さんは”接触”判定について記事を書いておられますが、私は今回”重なり”判定について記事を書きます。
私は”接触”,”重なり”の定義は次の画像が示す通りだと考えています。
それでは、筋道を説明いたしましょう。
(ⅰ)線分の始点または終点が円の範囲内であればその時点で return true
(ⅱ)線分の法線の中で、円の中心を通るものがなければその時点で return false
(ⅲ)「線分と、円の中心を通る法線の交点」が円の範囲内であれば return true
(ⅳ)return false
ある一箇所を調べてその時点で重なっているかどうか判断できれば即座に関数を脱出して結果を返す。
こうすることで、運がよければ非常に短い時間で判定することができます。
(ⅱ)について解説します。(ⅰ)を素通りしているということは以下のいずれかの状態であるということがわかります。
ここでは図の③の状態だとわかった場合に「重なっていない」と判定して脱出しているわけです。
あとは図の②か③のどちらかということになるので、これは交点と円との距離を調べればわかりますね。
というわけで、以下ソースコードです。
► スポイラーを表示
overlap.h
CODE:
#include
#include "typedef.h"
#include "pow.h"
#include "coor.h"
#include "line.h"
#include "cross.h"
#include "circle.h"
bool overlap(const fw::circle & circle, const fw::segment & segment){
const int r2 = fw::pow(circle.r, 2);
const int cx = circle.o.x;
const int cy = circle.o.y;
if(r2 >= fw::pow(segment.absolutebeg().x-cx, 2)+fw::pow(segment.absolutebeg().y-cy, 2) ) return true;
if(r2 >= fw::pow(segment.absoluteend().x-cx, 2)+fw::pow(segment.absoluteend().y-cy, 2) ) return true;
//この時点で線分の法線が円の中点を通らなければ重なっていない
fw::cross cross(fw::housen(segment, circle.o), segment);
if(cross.x>segment.absolutebeg().x && cross.x>segment.absoluteend().x) return false;
if(cross.x
X inline pow(X target, uint exponent){
if(exponent==0) return target;
for(uint i=0;i
struct coor{
T x;
T y;
coor(){}
coor & set(const T & x, const T & y){
this->x = x;
this->y = y;
return *this;
}
coor(const T & x, const T & y){ set(x,y); }
coor & operator() (const T & x, const T & y){ return set(x,y); }
coor & operator+= (const coor & another){
x += another.x;
y += another.y;
return *this;
}
bool operator== (const coor & another){
if(x != another.x) return false;
if(y != another.y) return false;
return true;
}
coor operator+ (const coor & another) const {
return coor(x+another.x, y+another.y);
}
coor operator- (const coor & another) const {
return coor(x-another.x, y-another.y);
}
};
}
line.h
CODE:
#include
namespace fw{
class horizon_error : public std::domain_error{ public:horizon_error():domain_error("fw_horizon_error"){} };
class vertical_error : public std::domain_error{ public:vertical_error():domain_error("fw_vertical_error"){} };
struct line{
public:
int x;
int y;
double a;
double b;
bool horizon() const { return mode==Horizon; }
bool vertical() const { return mode==Vertical; }
line(){ mode = None; }
virtual line & set(const coor & beg, const coor & end){
mode = None;
init(beg, end);
return *this;
}
line(const coor & beg, const coor & end){ set(beg, end); }
virtual line & operator() (const coor & beg, const coor & end){ return set(beg, end); }
int f(int x = 0) const {
if(vertical() ) throw vertical_error();
if(horizon() ) return int(b +this->y);
return int(a*(x-this->x)+b) +this->y;
}
int g(int y = 0) const {
if(abs(a)x);
// Then It's horizon.
throw horizon_error();
}
return int( (y-this->y -b)/a) +this->x;
}
protected:
static const uint Horizon = 0;
static const uint Vertical = 1;
static const uint None = 2;
uint mode;
void init(const coor & beg, const coor & end){
if(beg.x == end.x){
mode = Vertical;
a = 0.0;
b = beg.x;
}
else{
mode = Horizon;
a = (beg.y-end.y) / (beg.x-end.x);
b = beg.y - a*beg.x;
}
}
};
struct segment : public line{
public:
fw::coor beg;
fw::coor end;
segment(){}
const coor & relativebeg() const { return beg; }
const coor & relativeend() const { return end; }
coor absolutebeg() const { return beg+fw::coor(x,y); }
coor absoluteend() const { return end+fw::coor(x,y); }
segment & relativebeg(const coor & beg){ return relativeset(beg, end); }
segment & relativeend(const coor & end){ return relativeset(beg, end); }
segment & absolutebeg(const coor & beg){ return absoluteset(beg-fw::coor(x,y), end); }
segment & absoluteend(const coor & end){ return absoluteset(beg, end-fw::coor(x,y) ); }
segment & absoluteset(const coor & beg, const coor & end){
return relativeset(beg-fw::coor(x,y), end-fw::coor(x,y) );
}
segment & relativeset(const coor & beg, const coor & end){
this->beg = beg;
this->end = end;
init(beg, end);
return *this;
}
segment(const coor & beg, const coor & end){ relativeset(beg, end); }
segment & operator() (const coor & beg, const coor & end){ return relativeset(beg, end); }
};
struct housen : public line{
public:
housen(){}
housen & set(const fw::line & l, const fw::coor & dot){
if(l.horizon() ){
mode = Vertical;
a = 0;
b = dot.x - l.x;
return *this;
}
if(l.vertical() ){
mode = Horizon;
a = 0;
b = dot.y - l.y;
return *this;
}
a = -1.0/(double)l.a;
b = dot.y-l.y - a*(dot.x-l.x);
return *this;
}
housen(const fw::line & l, const fw::coor & dot){ set(l, dot); }
housen & operator() (const fw::line & l, const fw::coor & dot){ set(l, dot); }
};
}
cross.h
CODE:
namespace fw{
struct cross : public coor{
private:
static const bool Intersect = true;
static const bool Parallel = false;
bool mode;
double computeb(const fw::line & line) const {
return line.b+line.y + (-1)*line.a*line.x;
}
public:
bool intersect() const { return mode==Intersect; };
bool parallel() const { return mode==Parallel; };
cross(){}
bool compute(const fw::line & one,const fw::line & another){
if(abs(one.a-another.a) o;
int r;
circle(){}
circle & set(coor o, int r){
this->o = o;
this->r = r;
return *this;
}
circle(coor o, int r){ set(o,r); }
circle & set(int x,int y, int r){
this->o = coor(x,y);
this->r = r;
return *this;
}
circle(int x,int y, int r){ set(x,y, r); }
};
}
ソースコードの量は多いですが、実際の処理はそんなに多くないです。
おそらくline.hの中身が意味不明だと思いますが、
「座標x,yを保持し、それを基準とした相対的情報（傾き、切片、始点、終点）を記録する」
というコンセプトで作ったのですと言えば理解できる…かな…？
まあそんなわけで、これが私の回答です。
最近は専らActionScriptばかり書いていて、凄まじく久しぶりのC++だったのでなんだか初心に戻ったみたいで楽しかったです。
クラス定義の最後に;をつけ忘れてエラーが大量に出たときは懐かしくて噴き出したなんてことは決してありませんでしたからねｗ？
それでは、良いプログラミングライフを！
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター