Home CCW Algorithm
Post
Cancel

CCW Algorithm

CCW Algorithm

CCW Algorithm 이란?

  • CCW는 Counter ClockWise(반시계 방향)의 줄임말이다.
  • 일반적으로 선분의 교차 여부 판별등을 하는 것 같다.
  • 단순히 벡터의 연산을 CCW Algorithm으로까지 분류한 이유는 아직 궁금하다.

원리

  • 기본 원리는 벡터의 외적 연산을 기반으로 한다.
  • 단순히 세 점의 orientation을 보는 것이므로 연속된 두 점의 기울기를 측정한 뒤 기울기의 변화를 보는 것과 같다.

적용되는 기하 문제 유형

  • 다각형의 넓이 구하기
  • 정점의 위치판단
    • 다각형 내부/외부 위치 구분
  • Convex Hull 등등

Code

1
2
3
4
5
6
7
8
9
10
11
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
  int temp = x1 * y2 + x2 * y3 + x3 * y1;
  temp = temp - y1 * x2 - y2 * x3 - y3 * x1;
  if (temp > 0) {
    return 1;
  } else if (temp < 0) {
    return -1;
  } else {
    return 0;
  }
}

References

This post is licensed under CC BY 4.0 by the author.

#define vs typedef in C++

[노래][가사] 내가 죽으려고 생각한 것은