최근접 점 사이 거리 구하기

최근접 점 사이 거리 구하기

2차원 평면에 n개의 점이 입력으로 주어졌을 때 가장 가까운 점 사이의 거리를 구하는 문제

 

제일 먼저 입력값을 x축을 기준으로 오름차순 정렬

n개의 점을 반씩 분할(n // 2)하여 각각의 부분에서 최근접 점 사이의 거리를 구하고, 그 두 부분에서 각각 구한 거리를 비교해 더 짧은 거리를 dist라는 변수에 저장

참고) 알기 쉬운 알고리즘

 

 

여기서 주의할 점은 기준선 사이의 점들에 대한 거리값도 구해봐야 한다는 것

기준선(x축: n // 2, y축:0) 근처 x축 좌표 ± dist 안에 속하는 점들을 배열에 담고 그 속에서 dist보다 더 짧은 거리가 존재하는지 검사 후 작은 값을 dist_strip이라는 변수에 저장

기준선 사이 영역의 거리를 구할 때  x의 거리는 배열에 담으면서 추렸으니까 y를 기준으로 오름차순 정렬 후 두 점 사이 y 거리가 dist보다 짧은 경우일 때만 거리를 구해보면 됨

최종적으로 dist_strip 리턴

참고) 알기 쉬운 알고리즘

 

 

import math


# 두 점 사이의 거리
def distance(P1, P2):
    return math.sqrt((P1[0]-P2[0])**2 + (P1[1]-P2[1])**2)


# 기준선 사이 가까운 점들의 거리
# 두 점의 y사이의 거리가 dist(여기선 d)보다 작을 때 두 점 사이 거리 구하기
# 최소 거리는 계속 수정하면서
def strip_closest(P, d):
    n = len(P)
    d_min = d
    P.sort(key=lambda pt: pt[1])

    for i in range(n):
        j = i + 1

        # 한 점을 기준으로 남아있는 점들을 돌면서 두 점의 y 사이가 d_min보다 커지면 그 뒤의 점들은 당연히 다 d_min보다 크므로(y축 기준 정렬된 상태라) 더 볼 필요X, 반복문 탈출
        while j < n and (P[j][1] - P[i][1] < d_min):
            dij = distance(P[i], P[j])
            if dij < d_min:
                d_min = dij
            j += 1

    return d_min


# 최근접 점 사이 거리 구하기
def closest_dist(P):
    n = len(P)
    if n < 2:
        return float('inf')  # 큰 값이 되어야 나중에 함수(기준선 근처 거리)돌 때 min이 계속 수정됨

    elif n == 2:
        return distance(P[0], P[1])  # 좌표 두 개를 매개변수로 받아 거리구하기

    P.sort(key=lambda pt: pt[0])  # x를 기준으로 정렬

    mid = n // 2
    mid_x = P[mid][0]  # 기준선

    dist_left = closest_dist(P[:mid])
    dist_right = closest_dist(P[mid:])
    dist = min(dist_left, dist_right)

    Pm = []  # 가운데영역에 있는 점들을 담아둘 것
    for p in P:
        if abs(p[0] - mid_x) < dist:
            Pm.append(p)

    dist_strip = strip_closest(Pm, dist)  # 기준선근처 영역에서 dist보다 작은 값이 있으면 그 값을 리턴

    return dist_strip


# 실행
if __name__ == "__main__":
    p = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
    print("가장 가까운 두 점의 거리: ", closest_dist(p))

 

실행 결과