-
CCW(CounterClockWise) Algirothm
- 개념: 반시계 방향 알고리즘
평면 위에 놓여진 세 개의 점을 벡터의 외적을 이용해서 방향 관계를 찾는 알고리즘.
자세한 설명) https://degurii.tistory.com/47
- 2차원 평면상에 각각 x, y 좌표를 갖고 있는 세점 (p1, p2, p3)가 존재한다고 했을 때,
CCW 공식
s = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p1.y * p2.x + p2.y * p3.x + p3.y * p1.x)
만일 결과값 s가 0보다 작다면(s < 0) p1, p2 벡터를 기준으로 했을 때 p3는 오른쪽에 존재하는 정점(시계방향)이 되고,
s가 0보다 크다면(s > 0) p1, p2 벡터를 기준으로 했을 때 p3는 왼쪽쪽에 존재하는 정점(반시계방향)이 된다.
s가 0이라면(s == 0) 세 정점은 한 직선 위에 존재(평행)하게 된다.
- 관련 공식
사선공식(= 신발끈 공식) : 다각형의 넓이를 꼭지점의 좌표를 이용해 구할 수 있는 공식
https://ko.wikipedia.org/wiki/%EC%8B%A0%EB%B0%9C%EB%81%88_%EA%B3%B5%EC%8B%9D
- 관련문제
1. 방향 판단 [백준] 11758 CCW : https://www.acmicpc.net/problem/11758
2. 면적 구하기 [백준] 2166 다각형의 면적 : https://www.acmicpc.net/problem/2166
3. 선분 교차 여부 [백준] 12781 PIZZA ALVOLOC : https://www.acmicpc.net/problem/12781
이 문제에 대한 자세한 설명)https://jason9319.tistory.com/358