(알고리즘) 두 선분의 교차

알고리즘 문제를 풀면서 두선을 교차해서 교차여부를 확인하는 문제가 나왔지만 풀다가 시간초과로 인해

풀지 못했지만 다음에 기회가 생기면 풀 수 있도록 하기위해 블로그에 기록해서 남겨야할 필요성을 느꼈다. 

 

CCW

"평면에 놓여진 세 점의 방향관계를 구하는 알고리즘"

세 점이 주어져 있는 경우에, 이 점세개가 시계방향, 아님 반대 시계방향, 평행하는지 구하는 알고리즘으로

CCW 알고리즘은 시계반대방향일 때 양수, 시계방향일 때 음수, 평행일 때 0을 반환한다.

각각의 점을 P1(x1, y1) , P2(x2, y2), P3(x3, y3) 이라고 좌표를 두고, A,B,C 순서로 방향관계를 구한다면,

CCW 함수의 return값은 (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1) 이 된다

/*
- input : p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y2)
*/
int ccw(int x1, int y1, int x2, int y2, int x3, int y3){
    int cross_product = (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1);

    if (cross_product > 0){
        return 1;
    }
    else if (cross_product < 0){
        return -1;
    }
    else{
        return 0;
    }
}

 

 

교차여부 구하기

교차여부를 구하는 방법은 아래의 그림과 같이

• 위 그림에서 v1→v2로의 회전 방향은 반시계 방향이므로 ccw의 결과는 양수
• 반면 v1→v3로의 회전 방향은 시계 방향이므로 ccw의 결과는 음수
• 위와 같은 케이스의 선분의 교차에서는 위 방법으로 벡터 쌍들의 ccw를 구하고 그 방향이 다르면 선분이 교차한다.

예외 케이스

아래와 같이 서로 교차하지 않지만 두개의 방향이 다르지만 선분이 교차된다.

해결방안

방향을 바꾼후 교차 검증을 하게 된다면 확실하게 교차 여부를 알 수 있다.

v1->v2 시계 방향으로 됨으로 음수, v1->v3도 시계방향이 됨으로 음수가 된다.

• 즉, 여기 까지 정리하면 p1 - p2 - p3 의 방향과 p1 - p2 - p4의 방향이 반대이고 p3 - p4 - p1의 방향과 p3 - p4 - p2의 방향도 반대이어야 합니다.
• 함수로 정리하면 ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0이 되어야 합니다

출처: https://gaussian37.github.io/math-algorithm-line_intersection/ 게시글을 참고하여 작성됨.