기하알고리즘] 두 선분의 교차점 찾기

위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다.

이러한 두 선분의 교차점을 검사하는 방법으로는 다음과 같이 찾아 볼수가 있습니다.

1] 

각 선분에 대해서 그 선분을 포함하는 양방향으로 무한한 연장선을 긋고 그 두 연장선의 일차방정식을 구한 후에 그로부터 교점을 계산한다.

그 교점이 원래의 두 선분상에 있으면 두 선분은 교차한다.

2]

위의 그림에서 a,c,d,h 인 경우를 살펴보면 다음과 같은 규칙을 찾을 수 있습니다.

1. 선분 AB를 기준으로 볼때 점 C 점 D가 서로 반대편에 존재 하는지 검사

    선분 CD를 기준으로 볼때 점 A 점 B가 서로 반대편에 존재하는지 검사

2. 한 선분의 끝점이 다른 선분상에 존재 하는지 검사

3. 일직선상에 있으면서 한 선분의 끝점이 다른 선분상에 존재 하는지 검사

 

 

먼저 선분 AB에 대해 C의 점이 선분을 기준으로 왼쪽에 있는지 오른쪽에 있는지 판단하는 함수를 만들어 봅니다.

일반적으로 이러한 방향을 확인 하는 알고리즘을 ccw(counter clock wise) 라는 알고리즘으로 AB 두 선분에 C라는 점이 반시계 방향에 있으면 양수, 같은 직선상에 있으면 0, 시계방향에 있으면 음수를 리턴하여 방향을 판별하는 알고리즘을 많이 사용하게 됩니다.

 

일단 이러한 개념을 이해하기 위해서는 수학에서 벡터의 개념을 제대로 이해하고 넘어 오면 많은 도움이 되는데...

벡터의 개념을 이해하고 오지 못했다고 해도...

이러한 기하 알고리즘을 다루면서 나중에 수학을 배울때...

벡터란 것을 왜 배우고 이런곳에 사용되는지 알수 있기 때문에 훨씬 더 많은 흥미를 가지고 공부를 할 수 있을 것입니다.

 

일단 벡터라는 개념에 대해서는 나중에 기회 되면 다시 한번 설명을 하도록 하겠습니다.

위와 같이 (a) 형태에서는 음수 (b) 형태에서는 양수 (c) 형태에서는 0 이 리턴되는 형태를 CCW 알고리즘이라 한다.

 

그러면 이러한 CCW 함수를 만든다고 하면 다음과 같은 형태에서 교차점이 발생하는 것을 확인 할 수가 있습니다.

 

int CCW(struct point A,struct point B,struct point C)

{

   int dxAB = B.x - A.x;

   int dyAB = B.y - A.y;

   int dxAC = C.x - A.x;

   int dyAC = C.y - A.y;

   //시계 방향인 경우

   if(dxAB * dyAC < dyAB * dxAC) return -1;

   //반시계 방향인 경우

   if(dxAB * dyAC > dyAB * dxAC) return 1;

   //일직선인 경우

   return 0;  

}

위의 경우를 그림으로 그려 보면 다음과 같습니다.

선분 AB의 기울기는 dyAB / dxAB 로 나타낼수 있으며

선분 AC의 기울기는 dyAC / dxAC 로 나타낼 수 있습니다.

 

여기서 AB의 기울기와 AC의 기울기를 비교 하기 위해서

 dyAB/dxAB < dyAC/dxAC //AC의 기울기가 크므로 반시계 방향

양편에 dxAB * dxAC 를 곱해 보면

dyAB * dxAC < dyAC * dxAB //반시계 방향 

 

위와 같은 원리에 의해 CCW 알고리즘에 의해 AB 선분과 C의 점이 어느 위치에 있는지를 확인 할수 있는 알고리즘을 만들수가 있습니다.

 

이러한 방향을 이용해서 다음과 같이 교차점을 찾을 수가 있습니다.

1.AB 선분과 C 점의 방향 과 AB선분과 D 점의 방향이 서로 다른가? (방향이 서로 같다면 교차점은 생길수가 없습니다.)

2.CD 선분과 A점의 방향 과 CD선분과 B 점의 방향이 서로 다른가?

이 두가지를 만족한다면 맨 위의 그림의 (a) 와 같은 그림인것을 찾아 내는 것입니다.

이것을 판단하는 것은 다음과 같이 구현하면 될것입니다.

int intersection(struct line AB,struct line CD){

if( (ccw(AB.p1,AB.p2,CD.p1) * ccw(AB.p1,AB.p2,CD.p2) < 0) && //AB선분과 C점과 D점의 방향이 다른지 체크

   (ccw(CD.p1,CD.p2,AB.p1) * ccw(CD.p1,CD.p2,AB.p2) < 0 ) ) return true;

//여기부터는 한 점이 한직선에 만나는지를 체크하여 교차 여부 확인 예의 c,d,h 와 같은 경우 구현

//맨위의 c와 d의 그림인경우 AB선 위에 CD.p1 또는 CD.p2 가 기울기가 같거나 CD선 위에 AB.p1 또는 AB.p2 가 기울기가 같은 상태에서 그 직선 내에 점이 포함되어 있어야 한다. (아래 그림 참고)

if(ccw(AB.p1,AB.p2,CD.p1) ==0 && internalPoint(AB.p1,AB.p2,CD.p1) ) return true;

if(ccw(AB.p1,AB.p2,CD.p2) ==0 && internalPoint(AB.p1,AB.p2,CD.p2) ) return true;

if(ccw(CD.p1,CD.p2,AB.p1) ==0 && internalPoint(CD.p1,CD.p2,AB.p1) ) return true;

if(ccw(CD.p1,CD.p2,AB.p2) ==0 && internalPoint(CD.p1,CD.p2,AB.p2) ) return true;

return false;

}

위의 그림에서 보면 dxAB * dxAB + dyAB * dyAB > dxAC * dxAC + dyAC * dyAC 인것을 확인 할 수가 있습니다.

여기에서 dxAB * dxAB 처럼 제곱을 하는 이유는 값이 음수인 경우 절대값을 취하기 위해서입니다.

이것의 함수는 다음과 같이 만들어 볼수가 있습니다.

int internalPoint(struct point A,struct point B,struct point C)

{

   int dxAB = B.x - A.x;

   int dyAB = B.y - A.y;

   int dxAC = C.x - A.x;

   int dyAC = C.y - A.y;

   if((dxAB * dxAC <0) || (dyAB*dyAC<0) ) return 0; //서로 다른 방향이라면 포함하지 않는다

   if(dxAB * dxAB + dyAB * dyAB >= dxAC * dxAC + dyAC * dyAC ) return 1;

   return 0;  

}

 

위와 같은 원리로 두개의 직선이 교차가 되는지 혹은 한개의 직선에 어떤 한 점이 포함되는지의 원리를 알아 보았습니다.

 

우리가 중고등학교때 열심히 수학을 배우는 이유는 나중에 이러한 수학적인 부분을 기반으로 더욱 큰 그림을 그려 보기 위한 하나의 과정이라고 생각합니다.

 

저도 중고등학교때 수학을 배울때 이걸 왜 배워야 하는지 전혀 이유를 모르고...

거의 공식에 대입을 해서 문제를 풀고는 했던것 같은데요.

이러한 공부를 왜 해야 되고 나중에 어떤 곳에 사용해야 될지를 알고서 공부한다면 훨씬 더 도움이 될것 같아요.

 

이러한 계산 기하학 문제는 단순히 두 직선의 교차를 구하는 문제 뿐이 아니라 2D 3D 에서 그래픽에서 사용하는데 가장 기초가 되는 알고리즘이기도 합니다.

 

우리 학생들은 저와 같이 그냥 수학문제를 단순히 공식에 대입해서 문제를 풀기보다는...

공식을 암기 해야 하더라도 이러한 공식이 왜 나왔는지 원리를 한번쯤은 파악하고 나서 그 공식을 외운다면 나중에 공식이 도저히 생각 나지 않을때 원리를 차근차근 살펴 보면서 그 공식을 유도해 나갈 수 있을거라 생각 되네요.^^

 

무더운 날씨에 공부와 씨름중인 학생 여러분이 항상 건강하게 뜻하는 목표를 이룰수 있기를 기원합니다.

 

 

 

기하알고리즘이란? https://wondangcom.com/453?category=717978

두선분의 교점 찾기 https://wondangcom.com/466

반직선의 교점찾기1 https://wondangcom.com/903

반직선의 교점찾기2  https://wondangcom.com/930