点と線分の最近傍点

★は点と線分が最も近い場所
●はドラッグして動かせる。

点と線分の最近傍点の求め方は「点と直線」や「点と半直線」に少し手順が増えるだけになりますので、この記事では直線や半直線との違いの部分にフォーカスして解説していきます。

その為、この記事を読む前に、以下の記事を先に理解しておく事をお勧めします。

直線や半直線との違い

直線は無限に続く線、半直線は始点があり、一方に無限に伸びる線ですが、線分には始点と終点があり長さがあります。

点と線分の最近傍点を求める際には、始点と終点の存在を考える必要があります。

考え方

●を動かして確かめてもらいたいのですが、●が青い領域にあるとき
最近傍点の求め方は点と直線の最近傍点の求め方と同じになります。

しかし、●が赤い領域にある時は、線分の左端が最近傍点になり、黄色の領域にある場合は線分の右端が最近傍点となります。

つまり、点と線分の最近傍点を求めるには

●があるのは青の領域なのか、それとも赤なのか、はたまた黄色なのかを判定する必要があります。

それを判定するためにベクトルの内積を使います。

内積についてより詳しい説明はベクトルの内積の特性に記載していますので興味があれば読んでみて下さい。

赤？青？黄色？

$A$: 点
$P1$: 線分の始点
$P2$: 線分の終点

赤なのか？

まずは $点A$ が赤の領域にあるかどうかを判定します。

$\vec{v}$：線分の方向を表すベクトル
$\vec{a}$：線分の始点 $P1$ から $点A$ に向かうベクトル

$\vec{v}$ と $\vec{a} $ の内積の結果がマイナスであれば、$点A$ は赤い領域にある事になり、この時の点と線分の最近傍点は $点P1$ になります。

$ \vec{v} \cdot \vec{a} < 0 $ の時、最近傍点は $点P1$

黄色なのか？

次に $点A$ が黄色の領域にあるかどうかを判定します。

$\vec{v}$：線分の方向を表すベクトル
$\vec{a}$：線分の終点 $P2$ から $点A$ に向かうベクトル

$\vec{v}$ と $\vec{a} $ の内積の結果がプラスであれば、$点A$ は黄色の領域にある事になり、この時の点と線分の最近傍点は $点P2$ になります。

$ \vec{v} \cdot \vec{a} > 0 $ の時、最近傍点は $点P2$

赤でも黄色でもなければ青である

見た通りですが、 $点A$ が赤、黄色の領域になければ、青の領域にあることになります。

この場合、点と線分の最近傍点は点と直線の最近傍点と同じ方法で求まります。

サンプルコード

/**
  * 点と線分の最近傍点を取得する
  * @param p 点
  * @param seg 線分
  */
 export function getNearest(p:Vector2, seg:Segment) {

   // 線分の向きを表すベクトルをv
   const v = seg.v;

   // 線分の始点から点に向かうベクトルをa1
   const a1 = Vector2.sub(p, seg.p1);
 
   // v と a1 の 内積がマイナス = 点は線分の始点の外側にある = 線分の始点が最近傍点
   if (Vector2.dot(v, a1) < 0) {
     return seg.p1;
   }

   // 線分の終点から点に向かうベクトルをa2
   const a2 = Vector2.sub(p, seg.p2);

   // v と a2 の 内積がプラス = 点は線分の終点の外側にある = 線分の終点が最近傍点
   if (Vector2.dot(v, a2) > 0) {
    return seg.p2;
  }

   // 線分との最近傍点を求める
   const n = v.normalize;
   const dot = Vector2.dot(n, a1);
   return Vector2.add(seg.p1, n.times(dot));
 }