幅のある二つの線分の衝突判定

[坂本龍]

はじめまして。坂本龍というものです。現在、マウスを用いたシューティング風のゲームを作成しております。
件名にもございますが、「幅のある二つの線分の衝突判定」をＣ言語でおこなう方法について、質問しに参りました。
ネットで検索いたしましたが、通常の線分交差判定のアルゴリズムはいくつか見つけられたものの、それらを「幅のある線分」に応用したアルゴリズムは見つけられませんでした。
また、そのようなアルゴリズムを自作する能力も、私にはございません。
もしご存知の方がいらっしゃいましたら、そのアルゴリズムをＣ言語でお教えください。
引数は、double型の4つのX・Y座標と、double型の２つの幅値（半径）としてくださると助かります。
（double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4,double width1,double width2　など）
求めている判定を添付画像で示しておりますので、そちらをご参照の上、画像のとおりの判定が可能なアルゴリズムをお願いします。

なお、参考までに、この掲示板に掲載されていたアルゴリズムをもとに作成し、現在私が使用している「円と幅のある線分の衝突判定」のプログラムを示しておきます。

int segment_collision_detection(double x1,double y1,double x2,double y2,double width,double px,double py,double prange){
double dx=x2-x1;
double dy=y2-y1;
double x=x1-px;
double y=y1-py;
double a=(dx*dx+dy*dy);
width+=prange;
if(a==0.0)return (x*x+y*y<width*width);
double t=-(dx*x+dy*y)/a;
if(t<0.0)t=0.0;
if(t>1.0)t=1.0;
x+=t*dx;
y+=t*dy;
return (x*x+y*y<width*width);
}

[hide]

いっそのこと幅のある線分ではなく
長方形もしくは長方形と円の複合でいいのではないですか？

[yukihiro]

通常の線分同士の衝突判定を行い、
当たってないと判定されれば次に
各端点ともう一方の線分との距離 ＜ 幅
という判定を行えばいいのでは。

[katariya]

いっそのこと幅のある線分ではなく
長方形もしくは長方形と円の複合でいいのではないですか？

おそらくhideさんの言ったこれがベストかと思います。
長方形同士なら互いの各辺を線分交差判定で判定してあげれば出せます。

もし先が丸まっている場合は、

（１）先端同士が当たっている場合（互いの先端円の当たり判定）
（２）辺が交差している場合（互いの辺の線分を交差判定）
（３）先端と辺の当たり判定（線と円の当たり判定）

（３）だけ少し面倒ですが以下のサイトに詳しく載っています
http://torasukenote.blog120.fc2.com/blog-entry-55.html

基本複雑な図形は分かりやすい図形に分割して考え複合的に組み合わせることで、実装出来ます。
アルゴリズム的には以上のような形になります。

[坂本龍]

皆様ありがとうございます。
yukihiroさまのアイデアを採用いたしました。
具体的には次のとおりとなりました。

//座標 (x1,y1),(x2,y2) を結ぶ線分と座標 (x3,y3),(x4,y4) を結ぶ線分が交差しているかを調べる
//ただし、線分が重なっている場合(3点,4点が一直線上にある)、「交差している」、と判定します。
int intersection_detection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4){
//x座標によるチェック
if (x1 >= x2) {
if ((x1 < x3 && x1 < x4) || (x2 > x3 && x2 > x4)) {
return 0;
}
}
else {
if ((x2 < x3 && x2 < x4) || (x1 > x3 && x1 > x4)) {
return 0;
}
}
//y座標によるチェック
if (y1 >= y2) {
if ((y1 < y3 && y1 < y4) || (y2 > y3 && y2 > y4)) {
return 0;
}
}
else {
if ((y2 < y3 && y2 < y4) || (y1 > y3 && y1 > y4)) {
return 0;
}
}

if (((x1 - x2) * (y3 - y1) + (y1 - y2) * (x1 - x3)) * ((x1 - x2) * (y4 - y1) + (y1 - y2) * (x1 - x4)) > 0.0) {
return 0;
}
if (((x3 - x4) * (y1 - y3) + (y3 - y4) * (x3 - x1)) * ((x3 - x4) * (y2 - y3) + (y3 - y4) * (x3 - x2)) > 0.0) {
return 0;
}
return 1;
}
//Visual Basic Library
//http://www5d.biglobe.ne.jp/~tomoya03/sh ... tionEX.htm

//二つの幅のある線分の衝突判定
int segment_collision_detection_2(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double width1, double width2){
if(intersection_detection(x1,y1,x2,y2,x3,y3,x4,y4)){
return 1;
}
else if(segment_collision_detection(x1,y1,x2,y2,width1,x3,y3,width2)){
return 1;
}
else if(segment_collision_detection(x1,y1,x2,y2,width1,x4,y4,width2)){
return 1;
}
else if(segment_collision_detection(x3,y3,x4,y4,width2,x1,y1,width1)){
return 1;
}
else if(segment_collision_detection(x3,y3,x4,y4,width2,x2,y2,width1)){
return 1;
}
return 0;
}