서론
전에도 선분 교차 문제를 풀었던 기억이 있는데, 그때는 두 선분의 각 끝점의 위치만 주어지고 교차 여부를 0 또는 1로 출력하는 것이 다였다.
그러나 이번에는 다량의 선분을 뭉탱이로 입력받고, 교차된 선분들끼리 그룹핑하는 작업까지 추가되었다. 딱봐도 Union-Find를 사용하면 되는 직관적인 문제이기에 이 부분에서는 문제가 없었는데, 선분 교차 판정 방법을 살짝 까먹어서 다시 복습 겸 찾아보았다.
CCW 알고리즘
먼저 선분 교차 판정은 CCW(반시계방향) 알고리즘을 사용하는 것이 정석 풀이이다. 예전에 이 방법을 몰라서 선분끼리 기울기 구하고 난리치다 나누기 연산때문에 애먹은 기억이 난다. 아무튼 그렇게 하면 조건 분기가 매우 많아지고 오류도 생기므로 기왕이면 CCW를 사용하는 것이 낫다.
CCW란 한 벡터와 한 점이 주어졌을 때, 해당 점이 벡터의 시계방향에 위치해있는지, 반시계방향인지, 벡터 선상에 위치해있는지 판별하는 알고리즘이다.
벡터 AB와 점 C가 주어졌을 때, CCW를 계산하기 위해 다음 공식을 사용한다.
(BX-AX)*(CY-AY)-(CX-AX)*(BY-AY)
X와 Y는 각각 ~의 X/Y좌표를 의미한다.
위의 값이 양수면 CCW, 음수면 CW, 0이면 선상에 위치한 것이다.
그렇다면 두 선분을 CCW를 이용해서 교차 판정을 하는 방법은 어떻게 될까.
두 선분 AB와 CD가 주어졌을 때, 교차가 되기 위해서는 AB와 C, AB와 D에 해당하는 CCW를 구한 뒤 둘을 곱하였을 때 음수가 나와야 한다. 양수가 나오게 되면 AB에 대해 점 C, D 모두 한 쪽 방향에 위치하는 것이고, 이는 교차하지 않았다는 말이 된다.
다만 예외 사항이 있으므로 한 쪽만 고려하는 것이 아니라, CD에서 A, B를 봤을 때도 CCW끼리의 곱이 음수가 나와야 한다.
다만, CCW가 양수라면 교차하지 않았다는 것이 확실하지만 0이 나왔을 때는 불분명하다.
CCW끼리의 곱은 총 2번 구했을 것이다(선분 AB에서 한 번, CD에서 한 번). 만일 둘 중 하나만 0이고 나머지는 0이 아니라면, 0이 아닌 나머지가 음수이면 교차, 양수이면 비교차이다.
둘 다 0인 경우는 딱 두 가지이다. 4개의 점이 일직선 상에 위치할 경우와, 두 선분의 각 한 쪽 끝점이 직각으로 만날 경우이다. 사실 둘을 서로 나눠서 비교할 필요는 없고, x좌표끼리, y좌표끼리 비교만 하면 된다.
즉,
- 한 선분의 x좌표 중 큰 것보다 다른 선분의 x좌표 중 작은 것이 더 클 경우 (반대의 경우도 고려)
- 한 선분의 y좌표 중 큰 것보다 다른 선분의 y좌표 중 작은 것이 더 클 경우 (반대의 경우도 고려)
총 4번 비교하여 위 경우 중 하나라도 해당된다면 만나지 않는 것이다.
y좌표도 고려해야 한다는 사실을 잊는 바람에 WA를 3번이나 받았다... ㅎㅎ
Union-Find
이 알고리즘은 익숙해지는 것이 좋다. 해당 문제는 인덱스가 작은 것에 우선순위를 두면 되므로 rank 리스트는 만들 필요가 없다. Find함수에서 모든 root 값을 최신화시키기 위해 다음과 같이 재귀함수를 써야 사후 작업을 할 필요가 없어진다.
find(x):
if x!=root[x]:
root[x]=find(root[x])
return root[x]Union 함수는 일반형과 같다. rank 필요 없어서 편안
union(x, y):
x=find(x)
y=find(y)
if x==y:
return
elif x<y:
root[y]=x
blah blah
else:
root[x]=y
blah blah물론 그룹에 대한 개수 관리를 위한 리스트도 만들어야 한다. 이는 blah blah에서 관리해주고 결과값 출력 시 사용해주면 된다.
결론
두 선분 AB와 CD 교차 여부 알기 위해 계산해야 하는 값:
CCW 4번(AB와 C, AB와 D, CD와 A, CD와 B)
CCW AB와 C 구하는 공식: (BX-AX)*(CY-AY)-(CX-AX)*(BY-AY)
CCW에서 동일 선분으로 계산한 것(AB, CD)끼리 곱하였을 때:
둘 모두 음수: 교차
둘 중 하나라도 양수: 비교차
둘 중 하나만 0: 0이 아닌 나머지가 음수면 교차, 양수면 비교차
둘 모두 0: x좌표, y좌표끼리 비교하여 한 선분의 큰 값보다 다른 선분의 작은 값이 더 큰 것이 있는지 확인(4번 비교): 없으면 교차, 있으면 비교차
참고자료
사실 밑의 글을 참고하면 그림과 함께 자세히 설명되어 있어 더 잘 이해된다.
선분의 교차 여부 확인 by Jinsol Kim
문제
