線分上の最も近い点
「 線分ABと点Pが与えられたとき、AB上でもっともPに近い点を求めるには？ 」と質問されました。
なるほど、マウスカーソルの位置を線分上にフィットさせたいんですね。あ、それともGPSから取った座標を道路にフィットさせたい？
垂線をおろして交点を求めるだけの簡単なプログラムのように思えて、これはちょっと工夫が必要です。
ナイーブな解法
垂線をおろして交点を求めればいいわけです。ただし、もし交点がなければ線分の端点AかBのどちらかが答え。
実際に手順を書いてみましょう。
- ABの傾きaを求める。
- 垂線の傾きは -1/a。ただしABが垂直なら垂線の傾きは0。垂線の傾きをbとする。
- 点Pを通り傾きがbとなる直線を求める。【一次方程式を解く】
- ABを直線の式で表し、垂線との交点を求める。【連立一次方程式を解く】
- 交点の座標がAとBの間にあるなら、交点が求める点。
- 交点の座標がAの外側ならAが求める点、Bの外側ならBが求める点。
場合分けが多いですね。しかも、傾きがゼロであることの場合分けを忘れるとゼロ除算が飛びます。
しかもこの方式、平面図形の場合にしか使えません。空間図形になるとそもそも「垂線の傾き」という概念がないですから。
なんとかスマートなプログラムにできないか？
なります。ここで役に立つのが、高校で習ったベクトルです。思い出してみましょう。
ベクトルを使った（スマートな！）解法
ベクトルには内積がありましたね。内積からは cosθ が簡単に求まります。cosθ ってつまり垂線の足から原点までの距離です。これを使えば簡単に解けそうじゃありません？
手順を書き下ろしてみましょう。ベクトルxの長さのことを|x|と表現します。
- 線分ABを、基点Aとベクトルaで表す。AからPまでのベクトルをbとする。
- aとbのなす角をθとすると内積abは、|a||b|cosθ。これを|a|で割った |b|cosθ は、線分AB上に下ろした交点までのAからの距離を意味します。
- “距離”が 0 以下なら A が求める点、|a|以上ならBが求める点、0より大きく|a|未満だったら、A + a・(|b|cosθ/|a|)が求める点です。
これを実際にプログラムにしてみましょう。コツとして、ベクトルの長さ|a|を求めるには平方根計算が必要になるので、|a|2のまま扱った方が効率がいいという点に留意します（|a|2を出すだけなら内積a・aを求めるだけです）。
- ベクトルaはB-A。ベクトルbはP-A。
- 内積iはab。交点までの距離比率rはi/|a|2。
- rが0以下ならAを返す、1以上ならBを返す、それ以外ならA + r・aを返す。
C言語で書き下ろします。二次元ベクトルを表すvector2Dという型を用意して使っていますが、オブジェクト指向言語なら内積を求めるメソッド・引き算をするメソッドを用意することで三次元など一般的な次元にも対応可能。
typedef struct{
double x;
double y;
} vector2D;
vector2D nearest(vector2D A, vector2D B, vector2D P) {
vector2D a, b;
double r;
a.x = B.x - A.x;
a.y = B.y - A.y;
b.x = P.x - A.x;
b.y = P.y - A.y;
// 内積 ÷ |a|^2
r = (a.x * b.x + a.y * b.y) / (a.x * a.x + a.y * a.y);
if(r <= 0){
return A;
}else if(r >= 1){
return B;
}else{
vector2D result;
result.x = A.x + r * a.x;
result.y = A.y + r * a.y;
return result;
}
}
まとめ
座標情報を扱うのにベクトルは避けて通れません。
そしてそのために必要なノウハウは実は高校で教わっていました。ただ、 プログラミングの役に立つよと言われていなかった だけで。
是非、当時の教科書を引っ張り出してみてください。
そして、高校では習わなかった超重要なベクトル技法があります。 アフィン変換 です。タイトルは煽りでしたね。アフィン変換についてはまた記事を改めて。
* 座標系 - アフィン変換/平行移動だって変換行列で - Qiita
（本人ブログ記事 http://sampo.hatenadiary.jp/entry/20070626/p1 の改題再編集です）