概要
1本の線分と1点の頂点の間の最短距離を求める。
線分S \((x_0, y_0) - (x_1, y_1)\) と 頂点P \((x, y)\) の間の最短距離を求める時、以下のように求める
-
頂点P から 線分S に垂線が引ける場合は、点と直線の距離を解とする
-
垂線が引けない場合は、線分Sの端点のうちのどちらかと頂点Pの間の距離を解とする
垂線が引けるかは \(\mathbf{a} = (x_1 - x_0, y_1 - y_0)\), \(\mathbf{b} = (x - x_0, y - y_0)\) とする時、 \(0 \le \mathbf{a} \cdot \mathbf{b} \le \|\mathbf{a}\|^2\) を満たすことを確認すればよい。
点と直線の距離は \(\displaystyle \frac{|\mathbf{a} \times \mathbf{b}|}{\|\mathbf{a}\|}\) で求められる。
実装
def cross2(p, q):
return p[0]*q[1] - p[1]*q[0]
def dot2(p, q):
return p[0]*q[0] + p[1]*q[1]
def dist2(p):
return p[0]**2 + p[1]**2
# Shortest distance between a line segment (p0-p1) and a point x
def segment_line_dist(x, p0, p1):
z0 = (p1[0] - p0[0], p1[1] - p0[1])
z1 = (x[0] - p0[0], x[1] - p0[1])
if 0 <= dot2(z0, z1) <= dist2(z0):
return abs(cross2(z0, z1)) / dist2(z0)**.5
z2 = (x[0] - p1[0], x[1] - p1[1])
return min(dist2(z1), dist2(z2))**.5
# example
print(segment_line_dist((-1, -1), (0, 0), (1, 0)))
# => "1.4142135623730951"
print(segment_line_dist((0.5, 1), (0, 0), (1, 0)))
# => "1.0"
print(segment_line_dist((2, 2), (0, 0), (1, 0)))
# => "2.23606797749979"