点と線分の最近傍点と距離の計算

概要

点と線分の距離を求める方法。
2Dグラフィックスを扱うGUIを作成する際腐るほど使うわりに毎回忘れるのでメモしておく。
(線をクリックした場所に何かしたいときとか)

問題

ベクトル表記に関して: 点$V_0$を原点として点$V_1$を示すようなベクトルを$V_0 V_1$と表現し、その値は$V_1 - V_0$で計算する。

以下に示す図のように線分$AB$と点$P$が存在する状況で線分$AB$と点$P$の最短距離と最近傍点を計算する。

手順

1. 点と線分がどの位置関係にあるかを計算する。

まずベクトルの内積$AP\cdot AB < 0$ならばパターン①である。
そうでない場合、$BP \cdot BA < 0$ならばパターン②である。
上記2つに該当しない場合パターン③となる。

2. 各パターンそれぞれで計算方法が異なる。

2.1 パターン①の場合

最短距離: $||PA||$
最近傍点: $A$

2.2 パターン②の場合

最短距離: $||PB||$
最近傍点: $B$

2.3 パターン③の場合

内積を使って$||AI||$を求めた後に点$A$を基準にしてベクトル$||AI||$を加算することで求めることができる。

$\alpha$を線分$AP$と$AB$が織りなす角度とする。

||AI|| = ||AP||\cos\alpha \qquad \qquad \qquad (1) \\
AP\cdot AB = ||AP||\cdot ||AB|| \cos\alpha \qquad (2)

(1)と(2)より

AP\cdot AB = ||AB||\cdot ||AI|| \\
||AI|| = \frac{AP\cdot AB}{||AB||}

最近傍点は$$A + \frac{AB}{||AB||} \cdot ||AI||$$

距離は$||P - AI||$となる。

サンプルコード (Python)

import numpy as np
from numpy.linalg import norm

# a, b, pはそれぞれshape=(2,)のndarrayであると想定する
def calc_distance_and_neighbor_point(a, b, p):
    ap = p - a
    ab = b - a
    ba = a - b
    bp = p - b
    if np.dot(ap, ab) < 0:
        distance = norm(ap)
        neighbor_point = a
    elif np.dot(bp, ba) < 0:
        distance = norm(p - b)
        neighbor_point = b
    else:
        ai_norm = np.dot(ap, ab)/norm(ab)
        neighbor_point = a + (ab)/norm(ab)*ai_norm
        distance = norm(p - neighbor_point)
    return (neighbor_point, distance)