点と半直線の最近傍点
★は点と半直線が最も近い場所
●はドラッグして動かせる。
点と半直線の最近傍点の求め方は点と直線の方法と似ていますので、この記事では点と直線との違いの部分にフォーカスして解説していきます。
まだ点と直線の記事を見ていない場合は、まず点と直線の最近傍点をお読み下さい。
直線と半直線で異なること
直線は無限に続く線ですが、半直線には始点があります。
点と半直線の最近傍点を求める際には、半直線には始点があるという事を意識する必要があります。
考え方
●を動かして確かめてもらいたいのですが、●が青い領域にあるときは 点と直線の最近傍点の求め方と同じになります。
しかし、●が赤い領域にある時、最近傍点は半直線の始点の位置になります。
つまり、点と半直線の最近傍点を求めるには、●が青い領域にあるのか、それとも赤い領域にあるのかを判定する必要があります。
それを判定するためにベクトルの内積を使います。
赤なのか青なのか
$A$:半直線の始点
$B$:点の座標
$\vec{v}$:半直線の方向を表すベクトル
$\vec{b}$:半直線の始点から点Bに向かうベクトル
この時、 $\vec{v}$ と $\vec{b}$ の内積をとって、内積の値がプラスだったら $点B$ は 青い領域にあり、マイナスだったら赤い領域にあります。
内積の値がプラスかマイナスかでそんなことがわかるの?と気になる方はベクトルの内積の特性をご参照ください。
まとめると
$ \vec{v} \cdot \vec{b} <= 0$ の時、最近傍点は $点A$ である。
$ \vec{v} \cdot \vec{b} > 0$ の時、最近傍点は 点と直線の最近傍点の方法で求める。
となります。
サンプルコード
/**
* 点と半直線の最近傍点を取得する
* @param p 点
* @param ray 半直線
*/
export function getNearest(p:Vector2, ray:Ray) {
// 半直線の向きを表すベクトルをv
const v = ray.v;
// 半直線の始点から点に向かうベクトルをb
const b = Vector2.sub(p, ray.p);
// v と b の 内積がマイナス = 半直線の反対側に点がある = 半直線の始点が最近傍点
if (Vector2.dot(v, b) <= 0) {
return ray.p;
}
// 内積がプラス = 点と直線の最近傍点を求める
const n = v.normalize;
const dot = Vector2.dot(n, b);
return Vector2.add(ray.p, n.times(dot));
}