当たり判定のアルゴリズムを教えてください。

Question

状況によって３角形、５角形、９角形、●角形・・・
というような不定形なオブジェクトの当たり判定のアルゴリズムは
どのようにすればよいでしょうか？

clsdi99 · Accepted Answer

この手の判定をきちんとする場合は、幾何学系の計算が必要になってきます。

No1さんの仰るように、ゲームなど高速かつ簡易的に判定するのであれば、四角形同士のあたり判定がよいでしょう。
四角形同士は
r1.left < r2.right && r1.right > r2.left
&& r1.top < r2.bottom && r1.bottom > r2.top
で判定できます。

もし多角形や円などさまざまな形同士であたり判定するならば、それぞれの形状同士のあたり判定（交差・オーバーラップ）を実装しなくてはいけません。

具体的なコードを書くと長いので、アドバイスとして以下のようなクラスを作ってみてはいかがでしょう？

class line_seg
{
public:
bool hittest (const line_seg &);
bool hittest (const polygon &);
bool hittest (const circle &);
};

class polygon
{
public:
bool hittest (const line_seg &);
bool hittest (const polygon &);
bool hittest (const circle &);
};

class circle
{
public:
bool hittest (const line_seg &);
bool hittest (const polygon &);
bool hittest (const circle &);
};

あと、多角形同士の判定の場合、線分の交差判定のみでは、内包されるようなパターンの時にだめですので、気をつけてください。

amru05 · Answer

「衝突判定」「コリジョン」で検索すると多くの有用な情報が得られますので検索してみてください。
  http://www.gamespp.com/algorithms/collisiondetection/

 他の回答者と殆ど同じですが、一般的には、高速に判定するために簡単な方法で関係ない組み合わせを除き、その後は、線分交差が有れば衝突、ない場合でも内包されている場合は衝突、それ以外は衝突していない。。ような判定を行います。
１）高速な衝突しない図形判定
　　図形データをエリア分けしておき、離れているエリア図形とは衝突しないので除く。
　　同一エリアや隣接エリア図形とは、図形を円や長方形で近似した図形同士で簡単に衝突しない図形は除く。
２）１）で除かれなかった図形は衝突の可能性が有るので詳細な衝突判定を行う。

参考URL：http://hspwiki.nm.land.to/?%BE%D7%C6%CD%C8%BD%C4%EA

FAY · Answer

物体が移動することを考えると速度的に厳しいかもしれませんが・・・
当たり判定「されるもの」と「するもの」のリージョンをそれぞれ作成し、
その2つのリージョンで共有される領域があるかどうかを調べる方法もあります。

sha-girl · Answer

もしゲームのあたり判定であればグラフィックリソースとは別に
四角形のあたり判定属性を用意するのが普通。(3Dなら直方体)

n角形とm角形の辺り判定を厳密に判定するには
各線分が交差するかどうかをみていけば良いでしょう。

(ax1,ay1)-(ax2,ay2)・・・線分１
(bx1,by1)-(bx1,by1)・・・線分２
が交差する条件
(ay1-ay2)(bx1-ax1)-(ax1-ax2)(by1-ay1)・・・(1)式
(ay1-ay2)(bx2-ax1)-(ax1-ax2)(by2-ay1)・・・(2)式
(by1-by2)(ax1-bx1)-(bx1-bx2)(ay1-by1)・・・(3)式
(by1-by2)(ax2-bx1)-(bx1-bx2)(ay2-by1)・・・(4)式

(1)式*(2)式 <= 0 && (3)式*(4)式 <= 0
これがが成立するとき線分が交差します。

当たり判定のアルゴリズムを教えてください。

この手の判定をきちんとする場合は、幾何学系の計算が必要になってきます。

「衝突判定」「コリジョン」で検索すると多くの有用な情報が得られますので検索してみてください。

物体が移動することを考えると速度的に厳しいかもしれませんが・・・

もしゲームのあたり判定であればグラフィックリソースとは別に

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング