벡터의 외적과 CCW (Counter ClockWise)

 

 

 

 

목차

 

  여러 글을 보면서 제가 이해할 수 있는 수준까지 공부하고 정리한 내용입니다. 따라서 수학을 파볼려는 분 보다는, 기하 알고리즘 풀이를 위한 기본적인 이해용으로 보시는게 맞을 것 같습니다. 제가 수학을 매우 못하는 편이라 제가 이해할 수준으로 정리한 내용은 아마도 쉽게 정리된 내용일 것 같습니다. 공부 이유는 백준(솔브닥) 그래프가 안이뻐서 입니다. 틀린 내용 있을 시 댓글로 알려주세요.

기하학만 폭삭 주저앉아서 안이쁨.

 

벡터의 외적

outer product, cross product, vector product, 벡터곱.

기하학의 사칙연산이라 불리는 CCW를 설명하기 위한 사전 지식 입니다.

이하 bold 처리된 대문자 $\textbf{A}, \textbf{B}$는 벡터를 뜻합니다.

 

• 3차원 공간에 대해 정의된 벡터를 이용한 특정 연산이다.
• 따라서 2차원 공간의 벡터에 대해 적용하려면 z축을 0으로 두고 외적 연산을 진행하면 된다.
• $\textbf{A}=(x_1, y_1, z_1), \textbf{B}=(x_2, y_2, z_2)$ 라고 하자. 이 때 외적은 $\times$기호로 나타낸다(읽는건 "A cross B").
• 즉, $\textbf{A}\times\textbf{B}$는 $\textbf{A}$와 $\textbf{B}$의 외적을 나타낸다.
• $\textbf{A}\times\textbf{B}=(y_1z_2-z_1y_2, -(x_1z_2-z_1x_2), x_1y_2-y_1x_2)=(y_1z_2-z_1y_2, z_1x_2-x_1z_2, x_1y_2-y_1x_2)$ 이게 외적 공식이다.
  • 처음껀 x축 성분이 없고, 두번째껀 음수를 붙인상태로 y축 성분이 없고, 세번째껀 z축 성분이 없다. 그러니 하나만 규칙 파악하면 전체 공식을 외울 수 있다!
• 이 때, 2차원 평면상이라면 $\textbf{A}=(x_1, y_1, 0), \textbf{B}=(x_2, y_2, 0)$ 일 것이고,
  따라서 $\textbf{A}\times\textbf{B}=(0, 0, x_1y_2-y_1x_2)$ 가 된다.
• 두 벡터 $\textbf{A}, \textbf{B}$의 외적의 결과는 두 벡터에 동시에 수직이고 그 크기가 $\left|\textbf{A}\right|\left|\textbf{B}\right|\sin{\Theta}$ 인 벡터이다. 위의 $\textbf{A}\times\textbf{B}$ 결과에 z축 성분만 있는걸보면 두 벡터에 동시에 수직이라는 것을 알 수 있다. 또한 $|\textbf{A}\times\textbf{B}|$는 z축 성분만 있으므로 z축의 값 자체가 크기가 된다. $\left|\textbf{A}\times\textbf{B}\right|=x_1y_2-y_1x_2$ 이다.
• 이 때 외적의 크기는 두 벡터가 만드는 평행사변형의 넓이와 같다.

 

• 따라서 2차원 평면상의 두 벡터 $\textbf{A}, \textbf{B}$에 대해 $\textbf{A}$와 $\textbf{B}$가 이루는 각인 $\Theta$ 를 모르더라도 $\left|\textbf{A}\times\textbf{B}\right| = \left|\textbf{A}\right|\left|\textbf{B}\right|\sin{\Theta}=x_1y_2-y_1x_2$ 이므로 평행사변형의 넓이(면적)를 알 수 있다.
• 마찬가지로 두 벡터가 이루는 삼각형의 넓이도 알 수 있다. 이걸 활용하면 이제 2차원 평면상의 좌표 3개가 주어지면 그 세 점을 이루는 삼각형의 넓이를 구할 수 있다.
  • 세 점의 좌표가 $a=(x_1, y_1, 0), b=(x_2, y_2, 0), c=(x_3, y_3, 0)$ 이라할 때, $\textbf{A}=\vec{ab}=(x_2-x_1, y_2-y_1, 0), \textbf{B}=\vec{ac}=(x_3-x_1, y_3-y_1, 0)$ 이다.
  • 따라서 $\textbf{A}\times\textbf{B}=(0, 0, (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1))$ 
  • 점 $a, b, c$가 이루는 삼각형의 넓이는 $((x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1))/2$ 이다.

 

• 추가로 위에서 나온 $((x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1))/2$ 을 풀어써보면 $(x_1y_2+x_2y_3+x_3y_1-(y_1x_2+y_2x_3+y_3x_1))/2$ 가 된다. 이건 아래 그림과 같이 좌표들을 배치한 후 빨간 부분은 더하고, 파란부분은 빼준 후 2로 나눠준 것과 동일하다. 신발끈 처럼 생겨서 신발끈 공식(=사선공식, Shoelace formula)이라고 하고, 평면상의 3개의 점이 이루는 삼각형의 넓이 뿐 아니라, N개의 점이 이루는 다각형의 넓이도 이 신발끈 공식을 통해 계산할 수 있다. (Shoelace formula 위키)

• 벡터의 내적은 외적과 관계가 없다. 그냥 벡터의 여러 성질을 나타내기 위한 서로 다른 개념이다.

 

---

 

CCW (Counter ClockWise)

• 기하 알고리즘에서 덧셈뺄셈 수준으로 쓰인다는 녀석이다.
• 평면 위에 놓여진 세 점의 방향관계를 알 수 있게 해주는 알고리즘이다. 당장 이걸 어디다 쓰는지 감이 안올 수 있는데, 다음에 쓸 글인 선분(벡터) 교차 판정 알고리즘에도 쓰일 수 있고, convex hull 알고리즘에서도 쓰인다. 그 이상은 아직 저도 공부중이라 잘 몰라요 ㅠ
• CCW는 벡터의 외적을 이용하는 알고리즘이다. 사실상 외적이 CCW의 전부인 것 같다. 두 벡터 $\textbf{A}, \textbf{B}$에 대한 외적의 결과는 두 벡터에 동시에 수직인 벡터라고 했다. 그렇다면 외적의 결과로 나온 벡터의 크기야 어떻든, z축에서 +인지 -인지에 따라 $\textbf{A}$와 $\textbf{B}$의 방향관계를 알 수 있을 것이다.
• 위 벡터의 외적에서 설명했던 식을 안보고 내려왔을 수 있으므로 다시 적어보겠다.
  • 점 $a=(x_1, y_1, 0), b=(x_2, y_2, 0), c=(x_3, y_3, 0)$ 이라할 때, $\textbf{A}=\vec{ab}=(x_2-x_1, y_2-y_1, 0), \textbf{B}=\vec{ac}=(x_3-x_1, y_3-y_1, 0)$ 이다.
  • 따라서 $\textbf{A}\times\textbf{B}=(0, 0, (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1))$ 이다.
  • $\left|\textbf{A}\times\textbf{B}\right| = (x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1) = x_1y_2+x_2y_3+x_3y_1-(y_1x_2+y_2x_3+y_3x_1)$
• $\left|\textbf{A}\times\textbf{B}\right| = D$라고 해보자.
  • D>0 이라면 $\textbf{A}$를 기준으로 $\textbf{B}$는 반시계 방향이다.
  • D=0 이라면 $\textbf{A}$와 $\textbf{B}$는 평행이다.
  • D<0 이라면 $\textbf{A}$를 기준으로 $\textbf{B}$는 시계 방향이다.

 

• 자바 코드로 구현해보면 다음과 같다.

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class CCW {
    public static int getDirection(Point a, Point b, Point c) {
        Point[] arr = {a,b,c,a};
        int sum = 0;
        for (int i = 0; i < 3; i++) {
            sum += arr[i].x*arr[i+1].y-arr[i+1].x*arr[i].y;
        }
        return sum>0?1:sum<0?-1:0;
    }
}

 

  위는 신발끈 공식 적용해서 알아보기 쉽게 짜둔거고, 그냥 아래처럼 각 값을 받아서 위에 써둔 공식대로 계산해도 당연히 상관 없다.

long sum = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;

 

---

 

관련 알고리즘 문제

1. 백준 11758 - CCW

  위에 나온 설명 그대로 구현하면 된다.

 

2. 백준 2166 - 다각형의 면적

  위의 설명 중 나온 신발끈 공식 위키를 보고 그대로 구현하면 된다.

 

CCW 설명하다가 부가로 나온 다각형의 면적을 왜 관련 문제로 적어놨냐면, 사실 CCW 자체만 써서 풀 수 있는 기하학 문제는 거의 없다 ㅠ 다음에 작성할 선분 교차 판정 정도는 가야 관련 문제들이 나오기 시작한다.

 

 

---

 

References

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/

벡터의 외적 – findmean

 

https://degurii.tistory.com/47

[알고리즘] CCW로 세 점의 방향성 판별하기

 

https://gaussian37.github.io/math-algorithm-ccw/

CCW(counter clockwise)

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sallygarden_ee&logNo=221265467087 

벡터의 곱셈(내적과 외적)

 

https://en.wikipedia.org/wiki/Shoelace_formula

Shoelace formula - Wikipedia