소소한일상

선분과 점의 최단점(가장가까운점) 구하기

선분은 광선(직선)과의 차이점은 시작점과 끝점이 존재한다는 것이다.

그래서 3가지 상황을 고려해봐야 한다.

선분 양끝점을P0, P1 이라하고 임의의점 Q0, Q1, Q2가 있다고 가정하자.

광선에서 가까운점을 구할때처럼 투영해서 나온 위치를 찾는다고 한다면, Q0의 경우 선분 사이의 점이 아니게 된다.

따라서 Q0의 경우 선분위의 가장가까운점은 투영한위치의 점이 아니라 P0라고 할 수 있다.

Q1의 경우 투영한 위치에 해당하는점이 선분위에 존재함으로 광선의 경우와 같이 투영한위치의 점이 가장 가까운점 이다.

Q2의 경우 투영한위치가 선분밖에 있으므로 가장가까운점은 P1이라고 할 수 있다.

그렇다면 임의의점과 선분상의 가장가까운 점이 선분위에 있을지 밖에 있을지를 어떻게 판단 할 것인지 알아보자.

먼저 임의의점과 선분의점(P0)의 방향 벡터W를 구한다.

또한 P0과 P1의 방향벡터를 V라 하자

Q0 의 경우 선분의점(P0)과 Q0의 방향벡터 w1을 구할수 있다. (Q1 - P0)

w1과 V를 내적하게 되면 내적값은 0이하가 나올것이다. (두벡터의 각도가 90도를 넘기때문에)

따라서 W와 V를 내적한값이 0이하라면 선분의 바깥(왼편)에 있다고 할수있다.

Q1 의 경우도 마찬가지로 w2와 v를 내적해보면 나오는값이 0보다 클것이다.

여기서 한번더 고려해봐야 될 것이 임의의점이Q2일경우 여기서구한 w3벡터 또한 내적할시 0보다 클것이다.

그래서 임의의점이 P1의 범위가 넘어갔는지 어떻게 판단 할 것 인가를 생각해 봐야 한다.

W와 V를 내적한값이 V벡터의 길이제곱보다 크다면 해당점은 P1범위를 넘어갔다고 할 수 있다.

선분과 점의 최단거리(가장가까운 거리) 구하기

세가지 상황을 고려하여 최단점을 구했다면 거리도 쉽게 구할 수 있다.

광선과 점의 최단점(가장가까운점) 구하기

광선의 시작점 O 광선의 방향 D 벡터라 할때 점P와 가장가까운 광선위의 점을 구하는 방법

W벡터를 구한뒤 벡터 투영을 이용하면 구할 수 있다.

광선의 시작점과 투영된 벡터를 더하면 P'를 구할 수 있다.

 D가 단위벡터라면 |D|제곱은 생략 가능하다.

광선은 반직선이므로 투영된 위치의 점이 위와 같이 광선 범위 안에 있지 않다면

가장 가까운점은 광선의 시작점 O가 될 것이다.

값이 0보다 작을때 광선범위 밖의 점이 될 것이다.

광선과 점의 최단거리(가장가까운 거리) 구하기

P' 벡터를 구했다면 P에서 P'로가는 벡터의 거리를 구할수 있으므로 쉽게 거리를 구할 수 있다.

또는

피타고라스 정리를 이용하여 구할 수 도 있다.

※ 벡터 길이의 제곱은 그벡터를 내적한 값과 같다.

가까운 점을 구할때와 마찬가지로 값이 0보다 작을때 광선범위 밖의 점이 될 것이다.

따라서 광선의 시작점 과 임의의점을 연결한 벡터 W의 길이가 최단거리가 된다.

구와구의 교차판정은 2차원의 원과원의 교차판정에서 축이 하나더 늘었다고 생각하면된다.

두 구 중심사이의 거리가 각 구의 반지름을 더한값보다 크다면 교차안함, 같다면 딱붙은상태, 작다면 교차함 이라 할 수 있다.

구의 거리를 구하는 방법은 피타고라스정리로 간단히 구할수 있다.

또는

A B 방향 벡터를 구하여 거리를 구할수도 있다. A구의 센터가 Ca B구의 센터가 Cb라고 한다면

거리를 구했다면 거리와 A B 반지름 합을 비교하면 교차여부를 판별할 수 있다.

구와구의 교차는 간단한 수식인만큼 빠른 교차판정이 가능하다.

※ 제곱근 연산은 연산시간이 걸리는 편에 속하므로 제곱근을 하지않고 A B 반지름 합을 제곱하여 비교하면 연산량을 줄일수가 있다.