[백준] 30_1. CCW(Counter Clock Wise) 알고리즘 설명 | 수알못
17387번: 선분 교차 2
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.
www.acmicpc.net
설명
해당 문제는 CCW(Counter Clock Wise)라는 다소 생소한 알고리즘을 활용하여 풀 수 있는 문제입니다.
수학 벡터와 관련된 알고리즘이다 보니 포기가 마려웠지만 그래도 한 번 이해해보고자 하였습니다.
이번 글에서는 CCW 알고리즘에 대해 제가 이해한 과정을 최대한 풀어서 설명해 보겠습니다.
CCW는 어떤 알고리즘인가?
평면 위에 3개의 점이 주어졌을 때 세 점의 방향을 알 수 있는 알고리즘입니다.
나올 수 있는 방향은 총 3가지입니다.
- 반 시계 방향
- 직선
- 시계 방향
ccw의 알고리즘에서는 반 시계 방향일 경우 양수, 직선일 경우 0, 시계 방향일 경우 음수를 반환하도록 합니다.
(알고리즘 이름이 Counter Clock Wise(시계 반대 방향)인 이유가 반 시계 방향일 경우 양수를 반환해서이지 않을까 추측해 봅니다.)
뭔 소리인가 싶겠지만 그림을 보시면 쉽게 이해가 되실 겁니다.
그럼 이제 CCW는 어떻게 구현해야 되는가?
구현 방법은 벡터의 외적을 구하면 됩니다. 그게 뭔데
벡터의 외적이란?
벡터의 외적은 쉽게 말해 두 개의 벡터에 대해 모두 수직을 만족하는 벡터를 말합니다.
(벡터는 방향을 가진 선분으로 이해하시면 마음이 편합니다.)
위 그림에서 a벡터와 b벡터가 있을 때 두 벡터 모두 수직을 만족하는 벡터는 a X b 벡터와 b X a 벡터 총 두 가지가 나올 수 있습니다. (벡터 a, b의 외적은 a X b로 표기합니다.)
벡터의 순서에 따라 외적의 결과는 다르게 나옵니다. a X b != b X a
또한 두 외적은 서로 반대에 위치하기 때문에 부호도 항상 반대로 나오게 됩니다. (음수 and 양수)
위 그림에서는 a X b의 결과가 양수가 나오고 b X a의 결과는 음수가 나옵니다.
그 이유는 오른손 법칙에 의해서 알 수 있습니다.
쉽게 생각하여 위 그림의 오른손처럼 검지가 먼저 그다음 중지 순서(반 시계 방향)로 외적을 구할 경우 외적의 방향은 위를 향하며 이는 양수값이 나옴을 의미합니다. (항상 양수임을 보장하는지, 왜 양수가 나오는지는 잘 모르겠습니다)
결과적으로 두 벡터의 외적을 구하면 해당 값의 부호를 통해 방향을 알 수 있게 됩니다.
따라서 우리는 CCW 알고리즘을 구현하기 위해 벡터의 외적을 구해주는 것입니다.
지금까지의 내용을 정리하면 다음과 같습니다.
- ccw 알고리즘은 결국 벡터의 외적을 구하면 되는 알고리즘이다.
- 벡터의 외적은 두 벡터 모두 수직을 만족하는 벡터이다.
- 벡터의 외적은 두 벡터의 순서에 따라 2개의 결과가 나오며 두 결과의 부등호는 반대이다.
- 오른손 법칙 순서의 벡터의 외적은 방향이 위로 향하며 양수값이 나온다.
- 오른손 법칙은 반 시계 방향이다.
벡터의 외적 공식
이제 벡터의 외적을 구하는 식을 알아보겠습니다.
벡터의 외적에 대한 공식은 다양하지만 그중에서 제가 쉽게 이해한 행렬 표기법으로 알아보겠습니다.
(이해하시면 딱히 암기하지 않아도 공식을 구할 수 있게 됩니다.)
벡터 a, b의 외적에 대한 행렬식은 다음과 같습니다. (a1=x, a2=y, a3=z)
행렬식 : 해당 행렬을 대표하는 값 정도로 이해하고 넘어가시면 됩니다.
해당 행렬식을 구하는 공식은 다음과 같습니다.
하지만 너무 복잡하기에 좀 더 간단한 사루스의 법칙을 이용하여 공식을 구해보겠습니다.
먼저 기존 행렬식 옆에 행렬식의 1열과 2열을 붙여줍니다.
그다음 아래 그림처럼 같은 대각선에 있는 애들끼리 곱해준 뒤 ex) i x a2 x b3
빨간색 대각선의 합 - 파란색 대각선의 합
을 구해주면 됩니다.
식으로 보면 다음과 같습니다.
여기서 식을 더 간단히 만들 수 있습니다.
일단 i, j, k는 단위 벡터 즉 1이기 때문에 굳이 계산해주지 않아도 됩니다.
거기에 a와 b 벡터는 2차원 벡터값이기 때문에 z값이 0이 됩니다. 따라서 a3와 b3는 0이 됩니다.
이에 따라 다시 식을 만들어주면 다음과 같습니다.
이제 예시와 함께 CCW를 구현해 보겠습니다.
평면 위에 3개의 점 A(ax, ay), B(bx, by), C(cx, cy)가 있다고 가정하겠습니다. (순서 중요)
먼저 벡터 AB와 벡터 AC를 구해줍니다.
// AB = (bx - ax, by - ay)
// AC = (cx - ax, cy - ay)
// 구현 코드
data class Point(val x: Long, val y: Long)
fun getVector(a: Point, b: Point) : Point {
return Point(b.x - a.x, b.y - a.y)
}
이제 벡터 AB, BC의 외적을 구해줍니다.
// AB x AC = AB.x * AC.y - AB.y * AC.x
// 구현 코드
fun ccw(ab: Point, ac: Point) : Int{
val cross = ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
}
추가적으로 외적의 부호에 따른 반환값을 설정해 주면 끝입니다.
// 구현
fun ccw(ab: Point, ac: Point) : Int{
val cross = ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
if (cross > 0) return 1 // 반 시계
else if (cross == 0L) return 0 // 직선
else return -1 // 시계
}
전체 코드입니다.
// 구현
fun main() {
data class Point(val x: Long, val y: Long)
fun getVector(a: Point, b: Point) : Point {
return Point(b.x - a.x, b.y - a.y)
}
fun ccw(ab: Point, ac: Point) : Int{
val cross = ab.x * ac.y - ab.y * ac.x // 두 벡터의 외적
if (cross > 0) return 1 // 반 시계
else if (cross == 0L) return 0 // 직선
else return -1 // 시계
}
val AB = getVector(A, B)
val AC = getVector(A, C)
val ABxAC = ccw(AB, AC)
}
아래는 3개의 좌표를 통해 바로 외적을 구하는 코드입니다. 사실상 외적을 구하는 동시에 벡터 계산을 해주고 있습니다. 대부분 블로그에서는 아래의 식을 알려주고 있습니다.
// AB = (bx - ax, by - ay)
// AC = (cx - ax, cy - ay)
// 벡터와 외적을 동시에 구할 경우
fun ccw(a: Point, b: Point, c: Point) : Int{
// ab.x * ac.y - ab.y * ac.x
// = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
val cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
if (cross > 0) return 1 // 반 시계
else if (cross == 0L) return 0 // 직선
else return -1 // 시계
}CCW 알고리즘을 이해한 대로 글을 작성해 보았습니다.
혹시 잘못된 정보가 있을 경우 지적해 주시면 감사하겠습니다.