벡터의 외적을 이용하여, 평면상에 세 점이 주어질때, 점들의 위치관계를 파악할 수 있다.
점 세개로 선분 두개를 만들어서 CCW를 적용했을 때, 결과가 양수라면 회전 방향이 시계 방향인 것이다.
(참고로 벡터의 외적은 교환법칙이 성립하지 않는다.)
중학 수학에 사용했던 신발끈 공식을 생각하면 기억하기 쉽다.
또한 CCW를 위와 같이 선분들이 놓여져있는 상태를 파악할 때 사용할 수도 있고, 면적을 구할때도 사용할 수 있다.
특정 다각형의 면적을 구하고자할 때, 외부의 점을 잡고 다각형 상의 두개의 점을 순차적으로 이용해서 CCW를 돌려줘서 더하고, 그 결과에
절댓값을 취한 후에 2로 나누면 넓이를 구할 수 있다.
음수 결과와 양수결과가 중간중간에 상쇄되는 것을 이용한 것이다.
아래의 코드는, 세점의 위치관계를 CCW를 이용해서 파악해보는 것이다.
점 p1, p2, p3가 차례로 입력이 주어지면, 선분 p1p2에 대해서 선분 p2p3가 어떻게 놓여 있는지 알 수 있다.
동일선상에 있으면 0을 반환하고, 반시계 방향으로 위치해있으면 1을 반환한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include<iostream> using namespace std; int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) > 0) return 1; else if ((x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1) < 0) return -1; else return 0; } int main(void) { int x1, y1, x2, y2, x3, y3; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3; cout << ccw(x1, y1, x2, y2, x3, y3) << '\n'; return 0; } | cs |
'Computer Science > Algorithm Theory' 카테고리의 다른 글
Counting Sort (C++) (0) | 2019.08.23 |
---|---|
최대 공약수 gcd, 최소 공배수 lcm (0) | 2019.08.19 |
기하 및 그래프 알고리즘 간단 정리 (0) | 2019.08.17 |
선분 교차 판별 (0) | 2019.08.11 |
시간복잡도 (0) | 2019.08.10 |