선분과 선분 교차 검사 알고리즘

CCW(Counter Clockwise) 알고리즘을 활용.

 

CCW 알고리즘이란, 세 점의 상대적인 위치 관계를 나타낸 것으로 아래 그림 같이 3가지 경우가 있다.

 

 

각각의 경우를 판별하는 방법은 세 점으로 만들어진 두 선분의 기울기를 비교하는 것이다.

 

위에서 선분 ab와 bc 순으로 검사한다면 가장 왼쪽의 경우 ab의 기울기가 bc의 기울기보다 작으므로 Counterclockwise가 된다.

 

반대로 가운데의 경우 ab의 기울기가 더 크므로 Clockwise가 되며, 오른쪽과 같이 두 기울기가 같다면 Collinear가 된다.

 

선분 ab의 기울기를 x, 선분 bc의 기울기를 y로 놓고 정리하면

 

x < y  ->  Counterclockwise

x > y  ->  Clockwise

x = y  ->  Collinear 

---

CCW 알고리즘을 활용하면 아래와 같이 두 선분의 교차 여부를 알 수 있다.

 

1. 선분 AB, 선분 BC가 있다고 할 떄 먼저 선분 AB를 기준으로 선분 BC의 각 점에 대해 CCW 계산을 한다.
2. 계산된 두 값 서로 다르다면, 다시 말해 Clockwise, Counterclockwise인 경우가 둘 다 나왔다면 교차의 가능성이 있다.
3. 선분 BC를 기준으로 1~2번을 반복한다.
4. 3번도 통과되었다면 두 선분은 교차한다고 판단된다.

아래 그림과 같이 두 선분이 교차된다면 ABC는 Counterclockwise, ABD는 Clockwise로 서로 다르고, CDA는 Clockwise, CDB는 Counterclockwise로 서로 다르게 나온다.

 

만약 교차하지 않는다면 두 경우 중 한쪽은 같게 나온다.

 

아래의 경우 CDA와 CDB는 다르지만 ABC와 ABD는 같은 Clockwise이다.

 

 

참고자료:

https://www.geeksforgeeks.org/dsa/orientation-3-ordered-points/

Orientation of 3 ordered points - GeeksforGeeks