점들을 각도를 기준으로 정렬

참고
- https://mathsciforstudent.tistory.com/206#article-2-1-1--%EA%B7%B9-%EC%A0%95%EB%A0%AC
특정 좌표를 기준으로 했을 때의 각도 순으로 점들을 정렬한다.
각도 순으로 정렬해 두면, 각도를 기준으로 스위핑, 이분 탐색, 투 포인터 등등의 테크닉을 그대로 사용할 수 있다.
사실 보통 많이 쓰이는 것은 360도 범위에서 정렬하는 것이 아니라, 180도 범위의 점들만을 정렬하는 것이다. 주어진 점들중에서 가장 왼쪽, 또는 가장 아랫쪽에 있는 점을 기준으로 해서 나머지 점들을 각도순으로 정렬하게 되는 경우가 많은데, 이럴 때에는 나머지 점들이 모두 180도 범위 안에 들어있게 되기 때문이다.
180도 정렬이 360도 정렬보다 신경 쓸 부분이 적어서 간단하긴 한데, 360도 정렬도 알아야 하긴 하므로 360도 정렬을 기준으로 설명하겠다. 360도 정렬 코드가 있으면, 180도 정렬은 그대로 갖다 쓰기만 하면 된다.

정렬 기준 정하기

정렬 기준을 명확히 정하지 않으면 이후에 계속 헷갈리게 된다.
한가지 명확한 기준은, 기준점을 원점으로 놓았을때 atan2로 구해지는 각도를 기준으로 하는 것이다. atan2함수는 (-π,π] 범위의 값을 리턴한다.
- 이 기준으로 정렬하면 원점에서 왼쪽으로 뻗은 반직선에서 시작해서, 반시계방향으로 회전하는 순서로 정렬된다. x축 위에 있는 점들의 각도는 이렇게 정의된다: atan2(x<0,y=0)=π, atan2(x>=0,y=0)=0 .
그러나 이 기준대로면 정렬했을때 원점이 중간쯤에 오게 되는데, ( atan2(0,0)=0 ), 문제를 풀때에는 원점이 제일 앞에 오도록 정렬되는 것이 더 편리한 경우가 많다.
그래서 여기에서는 다른점들의 순서는 atan2과 동일하되, 원점만 가장 작은 값을 갖게 되도록 구현하기로 하겠다. 원하는 정확한 정렬 순서는
- 원점 < 3,4사분면 < x축의 +방향 < 1,2사분면 < x축의 -방향 이다

구현

기준점을 넘겨줬을때, 그 점을 기준으로 하는 각도를 비교할 수 있는 함수를 만들고 싶다.
- 즉, 이런 식으로 활용할수 있는 polar_angle_key 함수를 만드는 것이 목표이다.
  - ```
  def polar_angle_key(pole: Point) -> Callable[[Point], T]:
      ...
      
  # points = [(x1, y1), (x2, y2), ...]
  # pole = (px, py)
  sorted_points = sort(points, key=polar_angle_key(pole))
```

쉽게 찾아볼수 있는 자료들은 대부분 c++ 을 기준으로 설명되어있는데, c++은 문법적으로 정렬시에 비교함수를 사용한다. 그래서 보통 자료들은 기준점과 p1, p2의 방향관계를 리턴값으로 갖는 비교함수를 정의해서, 이것을 이용해서 정렬하도록 구현하고 있다.
하지만, 파이썬은 정렬시에 비교함수가 아니라 키 함수를 사용하므로 이러한 구현법과는 잘 맞지 않는다.
물론 functools.cmp_to_key라는 비교함수를 키 함수로 변환해주는 함수가 있기는 하다. 이것을 써서 구현하면 이런식이 된다.
- ```
def orientation(o, p, q):
    return (p[0] - o[0]) * (q[1] - o[1]) - (p[1] - o[1]) * (q[0] - o[0])


def polar_angle_key(o):
    def _comp(p, q):
        if (p <= o) != (q <= o):
            return -1 if p < q else 1
        return -orientation(o, p, q)

    return functools.cmp_to_key(_comp)
```
  - 참고 링크에 있던 cpp 코드를 파이썬으로 옮긴것인데, 이것은 -x방향 반직선 대신 -y축 반직선을 기준선으로 정렬된다. 위에서 얘기했던 대로 기준선을 atan2값을 기준으로 정렬하려면 if문 부분을 좀 바꿔주면 된다.
좀 더 효율적인 방법은, 그냥 키함수를 만들어주는 것이다.
u=p-o, v=q-o 라고 할때, 벡터곱의 부호를 확인하는 것은 ux*vy 와 uy*vx 의 크기를 비교하게 되는 것인데, 깔끔하게 이항시키면 uy/ux 와 vy/vx, 즉 기울기를 비교하는 형태가 된다. 그래서 키값을 그냥 uy/ux 로 써주면 깔끔해진다.
- 아래에 실제 구현에서는 y/x 대신에 -x/y를 쓰게 되지만 같은 원리이다.
이제 몇가지 신경 써야할 것들이 있다.
첫번째는 값이 실수형으로 나오는 것에 의한 실수 오차 문제인데, 이것은 의외로 별 문제가 없다
- 우선 생각할 것은, 이렇게 계산된 키값은 그냥 키 값끼리의 크기비교만을 위해서 사용된다. 키값을 다른 연산에 추가로 사용할 것이 아니기 때문에 크기 비교만 정확하게 된다면, 정밀도가 부족해도 아무 문제가 없다.
- 거의 모든 문제에서, 좌표값의 범위는 2^32 안으로 들어온다고 가정해도 무방하다. 왜냐하면 벡터곱을 통해서 방향성을 계산하려면 두 좌표의 곱셈 연산이 필요한데, 좌표값이 32bit를 초과하면, 곱한 값의 범위는 64bit를 넘어간다. 이것을 다루려면 대부분의 언어에서는 추가적인 처리가 필요햐지는데, 출제하는 입장에서 부담스러워진다.
  - 좀더 정확히는 좌표값은 2^31 이내여야 한다. 그래야, 두 값의 차로 주어지는 벡터 성분이 2^32 이내가 되고, 이것들을 곱해도 오버플로우가 나지 않기 때문이다. 대부분의 문제에서는 |x|,|y| ⇐ 1,000,000,000 으로 주어지게 된다.
- x,y값의 범위가 32bit 이내라면, 64bit실수형 기준으로 x/y와 (x+1)/y 은 언제나 구분되어 저장된다. 따라서 키 값끼리의 크기비교는 항상 정확하게 처리된다.
두번째 신경쓸 부분은, 원점을 기준으로 180도 회전한 방향에 놓여져 있는 점들에 대한 처리이다. (1,1)과 (-1,-1)은 같은 기울기를 가지므로 이를 구분해줘야 한다. 위에서 비교함수를 이용해서 작성한 코드에서, orientation값을 기준으로 리턴하기 전에 if문으로 미리 처리줬던것과 같은 처리가 필요하다.
- 간단한 방법은 기울기값에 추가 변수를 합해서 키값을 튜플로 만드는 것이다. atan2를 기준으로 정렬할경우, 키값은 4분면<3분면<1분면<2분면이 되어야 하므로, (sign(y), -x/y) 를 키값으로 하면 이 순서대로 정렬시킬수 있다.

여기에 y가 0인 경우까지 고려해주면 이렇게 구현할수 있다.

def polar_angle_key(pole=(0, 0)):
    def _key_func(p):
        x, y = p[0] - ox, p[1] - oy
        if y == 0:
            if x == 0:
                return (-2, 0)
            return (0, 0) if x > 0 else (2, 0)
        else:
            sign = -1 if y < 0 else 1
            return (sign, -x / y)

    ox, oy = pole
    return _key_func

튜플의 첫번째 값은, 원점(-2) < 3,4사분면(-1) < x축의 +방향(0) < 1,2사분면(1) < x축의 -방향(2) 가 된다

사실 이것으로도 이미 사용하기에는 충분하긴 한데.. 튜플을 쓰는것 조차도 비효율적이라고 생각한다면 억지로 하나의 값으로 처리하는 방법도 불가능한것은 아니다.
- 정수좌표만 주어지므로 |y|은 1이상이고, 그러면 x/y 가 가질수 있는 값의 범위는 x의 범위와 같다. x가 2^32보다 작으므로 그보다 훨씬 큰값 (예를 들면 2^34) 정도의 값을 계산해놓고, 1,2사분면일때에만 x/y에 더해주면 항상 1,2사분면일때의 키값을 3,4사분면일때보다 크게 유지해줄수 있다.
- 그러나, 이것은 또다른 문제를 초래하는데 x/y가 매우 작은 값이었다면 2^34를 더해주는 순간, 실수 오차가 생겨서 원래 값을 잃어버릴수가 있고 대소 비교가 정확히 안될 수 있다.
- 파이썬에서는 실수 대신에 다른 자료형을 쓰는 것밖에 다른 방법이 없다. (cpp의 long double처럼 128bit 실수형을 지원하는 언어라면 그냥 써도 될거 같다). 처음에 생각한 것은 Fraction 클래스를 사용하는 것이었는데.. 이것은 튜플을 쓰는것보다 속도가 더 느려졌다.
- 그러다 떠오른 아이디어는, 그냥 정수형을 사용하는 것이다. 큰 수 M을 미리 구해서, x//y가 아닌 (x*M)//y 의 값을 키로 사용하는것이다.
  - 정수나눗셈을 쓰면 소숫점 이하가 사라지므로 당연히 대소 비교가 안되지만, x에 미리 큰 값을 곱해준 뒤에 나눗셈을 처리하면 원래는 사라질 소수부분이 살아있게 된다.
  - M=2^32로 잡으면 (x*M)//y 의 값이 정확히 대소 비교가 가능하다.
- 이제 그러면 1,2사분면일 때에는 이 값에 2^66 정도의 값을 더해주면, 원래 계획한대로 튜플을 안쓰고도 360도의 모든 좌표를 정렬시키는 것이 가능하다.
- 코드는 이런 식
  - ```
  def polar_angle_key(pole=(0, 0)):
      def _key_func(p):
          x, y = p[0] - ox, p[1] - oy
          if y == 0:
              if x == 0:
                  return -lim * 2
              return 0 if x > 0 else lim * 2
          else:
              return -(x << 32) // y + (-lim if y < 0 else lim)
  
      lim = 1 << 65
      ox, oy = pole
      return _key_func
```
- 모든 점의 좌표값의 절댓값이 2^31 이하인 경우에, 키값의 범위는 다음과 같이 나온다
  - 원점:-4L < 3,4사분면:[-3L,-L] < x축의 +방향:0 < 1,2사분면:[L,3L] < x축의 -방향:4L

180도 정렬

처음에 정했듯이, 360도 정렬의 기준선은 x축의 -방향이다. 이말은, 점들이 2사분면과 3사분면에 모두 포함되어 있는 경우가 아니라면, 180도 정렬에도 그대로 사용 가능하다는 뜻이다.
주어진 점들 중에서, 가장 왼쪽에 있는점 또는 가장 아랫쪽에 있는 점을 기준점으로 놓고 나머지 점들을 정렬해야 하는 경우라면, 이 코드를 그대로 사용할 수 있다. 보통은 min(points) 를 기준점으로 잡아서 쓰면 된다.
이렇게 360도 코드를 그냥 써도 되지만, 180도 코드를 따로 만들면 코드가 훨씬 심플해지기는 한다. 180도 회전된 각도를 구분해줘야 할 필요가 없어지므로, 그냥 기울기 값만으로 비교하면 된다.
점이 1,2사분면에만 존재한다고 가정할 수 있으면, 즉, [0,π) 범위의 각도만을 정렬한다면, 아래처럼 작성할 수 있다.
- ```
def polar_angle_key(pole=(0, 0)):
    def _key_func(p):
        x, y = p[0] - ox, p[1] - oy
        return -INF if y == 0 else -x / y

    ox, oy = pole
    return _key_func
```
- 이 방식으로 360도 범위의 점을 정렬한다면, 1,2사분면의 점들은 x축의 양의 방향과의 각도를, 3,4사분면의 점들은 x축의 음의 방향과의 각도를 기준으로 해서 정렬되게 된다.
- 원점을 지나는 직선을 회전시키면서 스위핑하는 형태의 구현이 필요한 문제들이 있는데, 이럴때에 딱 맞아 떨어진다.

활용

단순 다각형 만들기

주어진 점들 중에서 가장 바깥쪽에 있는 점을 기준점으로 잡고, 나머지 점들을 정렬한 뒤에 순서대로 선분을 그어주면, 선분간의 교차가 일어나지 않는다. 즉, 이렇게 만들어진 패스는 단순 다각형을 이루게 된다.
이 때에 주의할 점은, 기준점에서부터 가장 각도가 작은 점이 여러개 있을 경우이다. 이 점들에 대해서는 기준점에서부터 거리가 가까운 순서대로 정렬해주어야 한다. 마찬가지로 기준점에서부터 가장 각도가 큰 점들이 여러개 있을 경우에는 기준점에서부터 거리가 먼 순서대로 정렬해주어야 한다.
관련 문제
- 단순 다각형: 여기에 해당되는 가장 표준적인 문제. 다만 점들을 출력하는게 아니라, 처음 리스트에서 점의 순서를 출력하기 위해서 코드가 조금 꼬여있다. 깔끔한 코드를 보려면 Convex Hull
- Convex Hull: 주어진 점들이 볼록껍질에 해당하는 점이 주어진다는 것이 다르지만, 동일한 알고리즘을 사용해서 풀면 된다

목차

점들을 각도를 기준으로 정렬

정렬 기준 정하기

구현

180도 정렬

관련 문제

활용

단순 다각형 만들기