한 점과 가장 가까운 곡선 위의 점 구하기

※ 매개변수로 표현할 수 있는 곡선 (ex. 베지에 곡선)의 경우만 다룸.

 

관련 글 :

2021.07.11 - [이론] - 곡선(Curve) & 스플라인(Spline)

곡선(Curve) & 스플라인(Spline)

 

문제

---

Q ) t에대한 다항식으로 이뤄져 있는 곡선 $q(t)$ 와 곡선 밖의 점 $P$가 있다. 이때 점 $P$와 가장 가까운 곡선 $q(t)$ 위의 점 $X$는 어떻게 구할 수 있을까?

 

곡선 $q(t)$를 2차원상의 3차 베지에 곡선이라고 하자. 그렇다면 $q(t) = a_0 + a_1t+a_2t^2+a_3t^3, t \in [0,1]$ 으로 표현할 수 있다.

 

이때 $q(t)$위의 한 점을 좌표로 나타내면 $(x(t), y(t))$ 라고 할 수 있다. 

 

점 $P$와 곡선$q(t)$ 위의 한 점과의 거리의 제곱은 다음과 같은 $f(t)$로 표현할 수 있다.

 

$f(t) = (x(t)-P_x)^2 + (y(t)-P_y)^2$

 

그러면 $f(t)$의 값이 최소가되는 $t$를 찾는다면 $P$와 가장 가까운 점$X$의 좌표를 구할 수 있다.

 

$ t \in [0,1]$에서 $f(t)$의 최소값은 구간의 양 끝이거나(즉 $t = 0,1$), $f(t)$의 극점 (즉 $f'=0$) 중 하나이다.

 

이제 $g(t) = f'(t)$라고 정의해주기로 하자.

(만약 유리(rational) 베지에 커브인 경우 $g(t)$를 다르게 정의한다. 이 경우 참고에 달아놓은 자료 참고.)

 

그렇다면 $g(t)=0$을 만족하는 $t$는 어떻게 구할까? 

 

 

 

루트 격리하기

우선 루트를 격리해야 한다. 이 경우 중근을 1개로 다루어야 하므로 스트룸 정리를 사용한다. 스트룸 정리에 대한 내용은 다음 글 참고

 

2021.08.13 - [수학] - 스트룸 정리 (Strum's theorem)

스트룸 정리 (Strum's theorem)

 

만약 구간 $[0,1)$에 근이 존재하지 않는다면 $t=0,1$의 값만 구해서 어떤 것이 최솟값인지 알아내면 된다. 근이 1개 이상 존재하는 경우 루트를 격리한다. 이때 격리된 구간을 $[a,b)$ 라고 하자.

 

 

 

 

계산할 필요 없는 근 제외하기

우리는 $t \in [0,1]$ 내의 $f(t)$의 최소값을 구하고자 한다. 그리고 $f(t)$의 최소값은 구간의 양 끝이나 아래로 볼록한 극점 중 하나이다. 다시 말하면 $g(t) = f'(t) = 0$인 $t$중 $f(t)$의 아래로 볼록한 극점만 찾으면 된다. 따라서 다음의 경우들은 제외된다.

근을 구할 필요 없는 경우

 

우리가 원하는 근은 다음과 같은 형태이다.

 

 

그리고 위와 같은 형태는 앞서 구한 구간 $(a,b]$에서 다음과 같은 성질을 지닌다.

$g(a) < 0 , g(b) > 0$

 

 

따라서 종합하자면 스트룸 정리를 통해 $g(t)$의 루트를 격리하고 격리된 구간 $(a,b]$ 에 대해 $g(a) < 0, g(b) >0$ 인 경우만 근을 구해주면 된다.

 

 

 

근 구하기

 

근을 구하는 방법은 다음 글을 참고

2021.08.29 - [수학] - 다항식의 근 구하기

다항식의 근 구하기

 

참고로 이미 앞선 조건에서 $g(a)g(b) < 0$ 임을 보장할 수 있으니 bracket을 사용하는 알고리즘을 쉽게 적용할 수 있다. 

 

$g(t_i) = 0$인 $t_i (i = 0,1,2,...,n)$를 구했다면 한 점과 가장 가까운 최소점은 $q(t_i), q(0), q(1)$중 하나일 것이다.

 

 

 

 

참고)

https://hal.inria.fr/file/index/docid/518379/filename/Xiao-DiaoChen2007c.pdf