[📚정보] 민코프스키 차이를 활용해서 최소접근벡터 구하기

[vertex(4321vertex)]

1.최소접근벡터

최소접근벡터는 위의 그림처럼 한 다각형을 다른 다각형과 접촉시키기 위해 움직여야 하는 최소거리의 벡터에요,

그리고 그러한 최소접근벡터의 길이를 구하면, 두 다각형 사이의 거리를 구할수 있어요

2.민코프스키 차이를 활용해서 최소접근벡터 구하기

https://gall.dcinside.com/mgallery/board/view/?id=game_dev&no=214749

민코프스키 차이와 볼록껍질을 활용한 충돌체크

민코프스키 차이에 대한 기본적인 설명은 위의 글에 있어요

위의 그림에서 연두색 다각형이 사각형-삼각형 방향의 민코프스키 차이에요,

그리고 위의 그림처럼 만약 사각형과 삼각형이 충돌하지 않았다면, 원점(0,0)은 민코프스키 차이 밖에 있어요

그리고 위의 그림처럼 사각형과 삼각형이 가장자리에서 만났다면, 원점은 민코프스키 차이의 가장자리에 있어요

즉 위의 그림처럼 사각형과 삼각형이 서로 접촉하지 않았다면 원점은 민코프스키 차이 밖에 있게 되고

이때 원점을 민코프스키 차이에 접촉시키기 위해서 최소거리로 이동해야하는 벡터가 바로 삼각형을 사각형에 접촉시키기 위해서 이동시켜야 하는 최소거리의 벡터가 되는거에요, 위의 그림에서 보라색 벡터에요

여기서는 사각형-삼각형 방향이니까, 삼각형을 사각형에 접촉시키기 위해 움직여야 하는 최소거리의 벡터가 되는거에요,

위의 그림은 반대로 삼각형-사각형 순서의 민코프스키 차이에요, 즉 원점을 민코프스키 차이에 접촉시키기 위해 최소거리로 움직여야하는 벡터는 사각형을 삼각형에 접촉시키기 위해 최소거리로 움직여야 하는 벡터가 되는거에요, 위의 그림에서 보라색으로 표시한 벡터에요

즉, 두 다각형의 민코프스키 차이를 구한다음, 원점을 민코프스키 차이에 접촉시키기 위해서 최소거리로 움직여야 하는 벡터를 구하면, 결국 한 다각형을 다른 다각형까지 접촉시키기 위해 최소거리로 움직여야 하는 벡터를 구할수 있어요,

그리고 이때 그렇게 구한 벡터의 길이를 구하면, 두 다각형 사이의 거리를 구할수 있어요

그리고 두 다각형의 민코프스키 차이를 구한다음, 볼록껍질 알고리즘을 사용해서 그렇게 구한 민코프스키 차이의 가장자리를 감싸는 다각형을 구하는 방법은, 앞에 올려놓은 글에 나와있어요

[링크]

그리고 사용되는 코드는 위의 링크에 있어요