線分同士の交点を取得するには、次のようにします。ちょっと長いですね。
// 点オブジェクト
struct Point
{
double x; // X成分
double y; // Y成分
};
// 線分オブジェクト
struct Line{
Point sp; // 始点
Point ep; // 終点
};
// 交点を求める関数(交点なし、もしくは平行の場合はfalseを返す)
bool GetCrossPoint(const Line& line1, const Line& line2, Point& pt)
{
// ** まず、それぞれの線分を線として交点を求める
// line1は垂直ではない(y軸に平行ではない)
if(line1.sp.x != line1.ep.x){
// 1の傾き
m1 = (line1.ep.y - line1.sp.y) / (line1.ep.x - line1.sp.x);
// 1の切片
b1 = line1.ep.y - (m1 * line1.ep.x);
// line2は垂直ではない(y軸に平行ではない)
if(line2.sp.x != line1.ep.x){
// 2の傾き
m2 = (line2.ep.y - line2.sp.y) / (line2.ep.x - line2.sp.x);
// 2の切片
b2 = line2.ep.y - (m2 * line2.ep.x);
// もし線が平行の場合は、交点はない
if(m2 == m1){
// 平行 ***
return false;
}
else{
// 直線の公式にのっとって、交点を算出
pt.x = (b1 - b2) / (-(m1 - m2));
pt.y = m1 * pt.x + b1;
}
}
// line2は垂直
else{
// line2は垂直なので、x値は変わらない
pt.x = line2.sp.x;
// 直線の公式に当てはめる
pt.y = m1 * pt.x + b1;
}
}
// line1は垂直(y軸に平行)
else{
// line2が垂直の場合、平行
if(line2.sp.x == line2.ep.x){
// 平行**
return false;
}
else{
// 2の傾き
m2 = (line2.ep.y - line2.sp.y) / (line2.ep.x - line2.sp.x);
// 2の切片
b2 = line2.ep.y - (m2 * line2.ep.x);
// line1は垂直なので、x値は変わらない
pt.x = line1.sp.x;
// 直線の公式に当てはめる
pt.y = m2 * pt.x + b2;
}
}
// **求めた交点が、それぞれの線分の領域に乗っているか
minX(line1.sp.x < line1.ep.x ? line1.sp.x : line1.ep.x);
minY(line1.sp.y < line1.ep.y ? line1.sp.y : line1.ep.y);
maxX(line1.sp.x < line1.ep.x ? line1.ep.x : line1.sp.x);
maxY(line1.sp.y < line1.ep.y ? line1.ep.y : line1.sp.y);
if(maxX >= pt.x && minX <= pt.x
&& maxY >= pt.y && minY <= pt.y
){
minX(line2.sp.x < line2.ep.x ? line2.sp.x : line2.ep.x);
minY(line2.sp.y < line2.ep.y ? line2.sp.y : line2.ep.y);
maxX(line2.sp.x < line2.ep.x ? line2.ep.x : line2.sp.x);
maxY(line2.sp.y < line2.ep.y ? line2.ep.y : line2.sp.y);
if(maxX >= pt.x && minX <= pt.x
&& maxY >= pt.y && minY <= pt.y
){
return true;
}
}
return false;
}
※ 解説
順番に見ていきましょう。
上の例では、まず渡された線分を線とみなして交点を算出した後、その点がそれぞれの線分の上に乗っているかを判定しています。
直線同士の交点の求め方は、学校で習われたかと思います。
それぞれの傾き(a、c)と、Y切片(b、d)を求められれば、交点を求めることができますね。
傾きとは、Xの増分に対するYの増分の割合ですので、ある線分上の2点(上の例では始終点)のY成分の差をX成分の差で割れば算出できます。
傾きを求められれば、Y切片は次の式で求めることができます。
これでそれぞれの線の公式を求め、交点を算出できますね。
しかしここで気をつけねばならないのは、X成分の差が0になる場合です。
傾きを求めるときにX成分の差で除算を行っていますが、分母が0になる計算をコンピュータで行うと、値が無限大、つまりオーバーフローを起こしてしまいます。
X成分の差が0、つまり傾きが無限大の直線というのは、Y軸に平行な直線のことです。
傾きが無限大の場合は、交点のX値は計算をせずに出すことができます。
というのも、傾きが無限の線はX値がどこまで行っても変わらないためです。
X値が出せれば、Y値はもう片方の線分の傾き・Y切片を求めて、『y = ax + b』の公式に当てはめれば算出することができます。
もう一つ気をつけなければならないのは、直線1と直線2が平行の場合です。
直線が平行の場合は、交点は存在せず、重なっているか重なっていないか、のみです。
今回は重なっているかどうかは判定せず、交点なし、という結果のみ返しています。
まとめると、次のパターンごとに交点を求めればよいということになります。
① ２線の傾きが違い、どちらも傾きが無限大ではない
② 線１の傾きが無限大、もう片方の傾きは無限大ではない
③ 線１の傾きは無限大ではなく、もう片方の傾きは無限大
※ それぞれ線１を求めた後に、線２と平行でないかをチェックする
以上の点に気をつけて交点を取得できたら、最後に交点がそれぞれの線分に乗っているかを判定しています。
下の絵を見てください。
求めた交点は、線分を無限に続く線とみなして求めた交点です。
あとはその点が始点・終点で作成される矩形領域内に存在すれば、それは線分上に乗っている点、ということになります。
2つの線分に交点が乗っていれば、それは2つの線分の交点である、ということになります。
上の例の関数では、戻り値に交点が存在するかしないか、しか返していませんが、交点なし・平行で重なっている部分あり・平行で重なっていない等で戻り値の値を変えれば、もっと多様な関数になると思います。
また、最後の線分上かどうかの判定をなくせば、仮想交点を求めることもできます。
用途により使い分けることができますね。
| 
