[알고리즘] CounterClockWise(CCW)

  목  차

• CCW 개요
• CCW의 기본 원리
• BOJ - CCW 알고리즘 문제 풀이
• CCW를 활용한 알고리즘 문제

 
 

---

 

  CCW 개요

 
CCW 알고리즘은 주어진 점들이 시계 반대 방향으로 정렬이 되어 있는지를 판단하는 알고리즘이다. 이 방법은 기하학적 알고리즘에서 중요한 역할을 하는데, 
 
예를 들면, A, B, C가 순서대로 주어졌을 때 선분AB에 대해서 C가 시계 반대 방향에 위치해 있는지, 시계 방향인지, 아니면 같은 선상에 있는지를 판별하는 방법이다.
 
 

 
 
 

---

 

  CCW의 기본 원리

 
벡터의 외적을 사용해서 외적의 결과가 양수일 경우는 반시계, 음수일 경우 시계 방향에 있다는 의미이다.
 
 
외적 공식은 다음과 같다.
 

 
 
 

---

 

  BOJ - CCW 알고리즘 문제 풀이: 11758

 
CCW는 공식만 알면 굉장히 쉽기 때문에 CCW 자체는 어렵지 않다.
 

let input = require('fs').readFileSync(
	'/dev/stdin'
	).toString().trim().split('\n');

const dots = []

for(let i = 0; i < 3; i++){
	const [x, y] = input[i].split(" ").map(Number);
	dots.push(x)
	dots.push(y)
}


function ccw(x1, y1, x2, y2, x3, y3){
	const result = (x2 * y3 - y2 * x3) - (x1 * y3 - y1 * x3) + (x1 * y2 - y1 * x2)
	if(result > 0) return 1
	if(result < 0) {
		return -1
	} else return 0
}

const [x1, y1, x2, y2, x3, y3] = dots

console.log(ccw(x1, y1, x2, y2, x3, y3))

 
 
 

---

 

  CCW를 활용한 알고리즘 문제

 
볼록한 껍질 알고리즘(Convex Hull Algorithm): 1708