Hausdorff distance

 

Hausdorff distance란?

메트릭(거리) 공간의 두개의 부분 집합들 사이의 차이를 측정.

[ 점으로 이루어진 두 집합 간의 거리를 결정하는 방식. ]

 

탄생 배경:

두 점 사이의 거리는 두 점의 최소거리(두 점을 양끝점으로 하는 선분 크기)로 표현 가능하다.

하지만 두개의 점들의 집합(ex. 2개의 다각형에서 각 다각형들의 꼭짓점 집합)사이의 거리를 측정하려하는데 

각 집합에서 나온 임의의 두점들의 거리가 가깝다고 해서 그 점들이 다른 집합의 모든 점들과 가깝다고 할수 없다.

그래서 최소 두점의 거리가 아닌 최대 거리를 사용하여 두 집합간의 거리를 구한다.

 

최대 거리를 이용하는 이유:

두 집합 A, B가 있을 때 A의 원소 ai, B의 원소 bi가 존재한다.

이때 distance(a3, b4)가 작다고 해서

distance(a3, b1), distance(a3, b2), distance(a3, b3)가 모두 작다고 할수없다.

따라서 두 집합의 가까움을 구할때는 최대거리를 사용한다.

(아래의 반례는 최대 거리를 사용하면 해결이 된다.)

 

최소 거리를 사용했을때의 반례

 

A와 C 집합의 distance(ai, ci)에서 가장 작은 거리가 존재하지만

ci와 가장 가까운 ai를 제외한 나머지 A의 원소들에 대해 거리가 멀다.

하지만 B는 distance(ai, bi)에서 가장 작은 값은 존재하지 않지만

A집합과의 거리가 C보다 더 가깝다.

 

 

 

 

 

 

 

Hausdorff distance를 완전 탐색으로 구하는 방법 의사코드:

표현 1:

Max( Max( Min( Distance( a, b ) for a in A ) for b in B ), Max( Min( Distance( a, b ) for b in B ) for a in A ) )

 

표현 2:

 h = 0
for every point ai of A,
    shortest = Inf ;
    for every point bj of B
        dij = d (ai , bj )
        if dij < shortest then
            shortest = dij

    if shortest > h then
        h = shortest

 

 

실습:

A = [(0, 0), (1, 0)]

B = [(1, 0), (2, 0), (3, 0)]

 

답: 3

 

 

참고자료:

https://progworks.tistory.com/72

https://beguru.tistory.com/50

https://qastack.kr/codegolf/49093/compute-the-hausdorff-distance