概要

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"

Verified

  • AOJ: "1283: Most Distant Point from the Sea": source (Python3, 21.95sec)