line Intersect

line Intersect

컴퓨터 응용에서 기하학적인 문제를 해결하기 위해서는 

연산의 단순화 과정이 중요하다. 

기하적인 알고리즘들의 해결에서 직선 교차는 단순화를 위해서 제법 많이 사용된다.

실제 CAD 응용프로그램에서도 직선으로 표현하고 처리하는 비중이 크다.

이 글에서는 직선의 교차판단에 과정을 순서대로 설명한다(응용에 따라서 중간 과정이 필요없을 수도 있다).

1. Filter Box Intersect

두 개의 직선의 교차를 알기 위해서, 가장 먼저해야할 일은,

Box 교차를 판단하는 것이다. Box 는 직선의 두 점으로 구성되는 MBR이다.

Box 교차를 먼저 파악하는 이유는 교차하지 않는 두 직선을 빠르게 필터하기 위함이다.

이는 직선이 아니라, 곡선일 경우에는 더 효과적이겠다.

단순히 하나의 MBR 최소점보다 다른 하나의 최대점이 작은지를 판단하면 된다(disjoint).

(tol = tolerance)

a.min[0] > (b.max[0] + tol) ||  a.min[1] > (b.max[1] + tol) || a.min[2] > (b.max[2] + tol) ||

b.min[0] > (a.max[0] + tol) ||  b.min[1] > (a.max[1] + tol) || b.min[2] > (a.max[2] + tol)

2. Filter Singleton

하나의 직선이 길이가 0이라면, 직선 위에 있는지 판단하거나, 조건에 따라서는 필터할 수 있다.

길이가 있는 직선을 A, 길이가 없는 직선을 B 라고 한다면,

먼저, B의 한점과 가장 가까운 A선상의 점을 찾는다.

A 벡터와 A 시작점부터 B의 한점까지의 벡터의 내적값을 계산한다.

A 시작점에서 A벡터방향으로 내적값을 곱하여, 선상에 한점을 계산한다.

그리고 선상에 한점과 B의 한점과 같은지를 판단하여, 같다면 선상에 한점이 있음을 판단할 수 있다.

3. Filter Plane

다음은 평면에 대한 필터이다. 응용에 따라 다르겠지만, 

같은 평면의 직선의 교차를 판단한다고 할때, 삼중합(scalar triple product)을 응용할 수 있다

두 직선 A,B의 외적 벡터와 A시작점에서 B시작점 방향의 벡터의 내적값이 없다면(외적 1.0보다 작다면) 

같은 평면으로 판단할 수 있다.

4. Filter Parallel

두 직선이 평행이라면 상대 직선상에 점이 있는지를 판단하여 Colinear한지를 판단해야한다.

이는 Filter Singleton에서 직선위에 있는지 판단하는 것과 비슷한 방식으로 가능하다.

Colinear하지 않고, 평행하다면 두 직선은 만날일이 없다.

5. intersect

이제 드디어, 두 직선의 교차점을 계산할 수 있다.

상기 모든 필터를 거침으로써, BOX교차가 있고, 두 직선은 길이가 있으며

같은 평면상에서 평행하지 않다라는 조건이 있다.

같은 평면임으로 두 직선의 벡터를 각 X,Y축으로 가지는 평면으로 Transform한뒤

2차원 벡터의 내적으로 곱의 순서를 바꿀 때, 동일한 부호를 가지면 최종 교차로 판단할 수 있고

해당 내적값으로 교차점을 계산할 수 있다.

참조

http://omega.albany.edu:8008/calc3/triple-product-dir/cornell-lecture.html

http://www.math.ucla.edu/~ronmiech/Calculus_Problems/32A/chap11/section4/708d29/708_29.html

https://ko.wikipedia.org/wiki/%EC%82%BC%EC%A4%91%EA%B3%B1

http://bowbowbow.tistory.com/14