CounterClockWise

목표: 여러 점이 주어졌을 때 어떤 방향으로 진행하는지 결정한다.

CounterClockWise(CCW)는 카를 프리드리히 가우스의 Shoelace 공식을 기반으로 한다.

  1. 첫 번째 x 좌표를 두 번째 y 값과 곱하고, 두 번째 x 좌표를 세 번째 y 값과 곱한다. 이 과정을 모든 원하는 점에 대해 반복한다.
  2. 점들이 반시계 방향으로 순차적으로 라벨링되어 있다면, 위의 행렬식들의 합은 양수다. 절대값 기호는 생략할 수 있다. 만약 점들이 시계 방향으로 라벨링되어 있다면, 행렬식들의 합은 음수다. 이 공식은 그린의 정리의 특수한 경우로 볼 수 있다.

Shoelace

다음은 이해하기 쉬운 Swift 구현이다:

func ccw(points: [Point]) -> Int{
  let polygon = points.count
  var orientation = 0

  for i in 0..<polygon{
    orientation += (points[i%polygon].x*points[(i+1)%polygon].y
      - points[(i+1)%polygon].x*points[i%polygon].y)
  }
    
  switch orientation {
  case Int.min..<0:
    return -1 // if operation < 0 : ClockWise
  case 0:
    return 0 // if operation == 0 : Parallel
  default:
    return 1 // if operation > 0 : CounterClockWise
  }
}

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트한다:

var p1 = Point(x: 5, y: 8)
var p2 = Point(x: 9, y: 1)
var p3 = Point(x: 3, y: 6)

print(ccw(points: [p1,p2,p3])) // -1 means ClockWise

이 함수는 [Photo]가 주어졌을 때, Shoelace 공식에 따라 주어진 점들의 방향을 계산한다.

orientation이 0보다 작으면 방향은 시계 방향이다.
orientation이 0이면 방향은 평행하다.
orientation이 0보다 크면 방향은 반시계 방향이다.

예제

삼각형

var p1 = Point(x: 5, y: 8)
var p2 = Point(x: 9, y: 1)
var p3 = Point(x: 3, y: 6)

print(ccw(points: [p1,p2,p3])) // -1은 시계 방향을 의미

triangle

triangleExpression

사각형

var p4 = Point(x: 5, y: 8)
var p5 = Point(x: 2, y: 3)
var p6 = Point(x: 6, y: 1)
var p7 = Point(x: 9, y: 3)

print(ccw(points: [p4,p5,p6,p7])) // 1은 반시계 방향을 의미

Quadrilateral

triangleExpression

오각형

var p8 = Point(x: 5, y: 11)
var p9 = Point(x: 3, y: 4)
var p10 = Point(x: 5, y: 6)
var p11 = Point(x: 9, y: 5)
var p12 = Point(x: 12, y: 8)

print(ccw(points: [p8,p9,p10,p11,p12])) // 1은 반시계 방향을 의미

triangle

triangleExpression

실제 문제에서 CCW를 사용할 일은 거의 없지만, 기하학 알고리즘을 다루는 것은 재미있다. 이 공식은 1769년 마이스터(1724-1788)와 1795년 가우스에 의해 설명되었다. 다각형을 삼각형으로 나누어 검증할 수 있으며, 그린 정리의 특수한 경우로 간주할 수 있다.

Swift Algorithm Club을 위해 TaeJoong Yoon이 작성