[알고리즘/Python] CCW 알고리즘 : 벡터의 외적

 

---

CCW 알고리즘이란 ? 

 

Counter Clockwise의 약자로 세 점의 방향성을 구하는 알고리즘이다! 즉, 평면상에 존재하는 세 점에 대해서 위치 관계를 알 수 있는 알고리즘임 ~ 

 

결론만 먼저 말해보자면 세 점 A(x1,y1), B(x2, y2), C(x3, y3)이 주어졌을 때 , 점 A,B,C를 순서대로 봤을 때 반시계 방향이면 양수를, 시계 방향이면 음수를, 직선상에 있으면 0을 반환한다. 

CCW 공식 : (Bx-Ax) * (Cy-Ay) - (Cx-Ax) * (By-Ay) 

---

벡터의 외적(Cross product) 

 

CCW 알고리즘에 관한 증명 

기하 알고리즘에서 필수적으로 알아야한다는 기초적인 개념인 외적, 열심히 배워보고 까먹지 않도록 하자 ~ 

이 경우에서 점 C는 선분 AB의 반시계방향에 위치하고 있다.

이 때 벡터 u와 벡터 v가 이루고 있는 각 θ는 0<θ<180˚이므로 sinθ >0이다. → 즉, 반시계 방향에 위치하면 양수 

벡터 u와 v가 이루고 있는 각 θ가 180<θ<360˚이면 sinθ<0이다. → 즉, 시계 방향에 위치하면 음수가 나옴

벡터 u와 v가 이루고 있는 각 θ가 0˚ 또는 180˚이면 sinθ =0이다. → 즉, 일직선에 위치하면 0이 나옴 

 

* 벡터의 외적 공식 

 

- (정의 1) 두 벡터의 외적은 단위벡터와 행렬식으로 구할 수 있다. 

 

- (정의 2) 두 벡터의 외적은 평행사변형의 넓이와 같다 

- (정의 3) 두 벡터가 이루는 각은 다음과 같다 

 

** 외적은 교환 법칙이 성립하지 않는다. AB 와 BA는 다른 것이다 (방향성이 있기 때문에)

 

사진 출처 :

http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/

 

---

관련 문제와 기본 코드 

 

백준 11758 

코드 

x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())
x3, y3 = map(int,input().split())
check = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)

if check > 0 : # 외적이 양수인 경우 반시계방향을 나타냄
    print(1)
elif check == 0 :# 외적이 0인 경우 일직선상에 있음을 나타냄
    print(0)
else: # 외적이 음수인 경우 시계방향을 나타냄 
    print(-1)

CCW 기본 공식을 이용해서 풀 수 있는 비교적 쉬운 문제다 ~ 

 

---

[참고 및 출처]

 

https://johoonday.tistory.com/102

http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/

한국항공대학교  「문제해결기법」 강의자료