점과 선분 사이의 거리

0 이상 1 이하의 실수 t에 대하여 선분 AB를 t:(1-t)로 내분하는 점을 Q라고 하자. 선분 PQ의 길이를 f(t)라고 할 때, 함수 f는 아래로 볼록함을 알 수 있다. (즉, f''(t) >= 0)

함수 f의 최솟값이 점 P와 선분 AB 사이의 거리가 되고, 이는 이분탐색을 통해 구할 수 있다.

def dist(P, A, B):
    for i in range(100):
        if (P.x - A.x) ** 2 + (P.y - A.y) ** 2 > (P.x - B.x) ** 2 + (P.y - B.y) ** 2:
            A = (A + B) / 2
        else:
            B = (A + B) / 2
    dist = ( (P.x - A.x) ** 2 + (P.y - A.y) ** 2 ) ** 0.5
    return ( dist )

점과 직선 사이의 거리를 응용하면 이분탐색을 하지 않고 거리를 구할 수 있다.