테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 다각형 (Polygon) ======
  * 놀랍게도 '다각형'의 정의는 한 평면 위에 있으면서 유한개의 선분들이 차례로 이어져 이루어진 경로이다. 변들끼리 교차하더라도 다각형이 될 수 있다.
  * 우리가 보통 생각하는 형태의 다각형, 즉 변들이 꼭짓점에서만 만나는 다각형은 '[[wp>simple polyong|단순 다각형 (Simple polygon)]]'이라고 한다.
    * 이에 해당하지 않는 다각형, 즉, 변들끼리 교차하는 다각형은 [[wp>List of self-intersecting polygons|self-intersecting polygons]]' 이라고 부른다. 한국어로는 단순하지 않은 다각형이라고 부르는 것 같다.
  * 하지만 매번 단순다각형과 단순하지 않은 다각형을 구분해서 부르는 것은 너무 번거롭다. 그냥 여기에서는 '다각형'이라고 하면 단순다각형을 말하는 것으로 하겠다.
    * 이후에 설명할 다각형에 대한 알고리즘이나 정리들은, 따로 언급이 없으면 단순 다각형에 대해서 성립하는 것으로 이해하자. 단순하지 않은 다각형에 대해서는 성립할 수도 있고 안할수도 있다.

===== 성질 =====
  * 다각형의 내각의 합은 180° * (n−2)

===== 다각형 자료형 =====
  * 직관적이고 가장 흔한 방식은 꼭지점들을 인접한 순서대로 배열에 저장하는 것이다.
  * <dkpr>
Polygon: TypeAliase = Sequence[Point]
</dkpr>
  * 방향성까지 강제하는 것(예를 들면 시계반대방향 순서로) 은 몇몇 알고리즘을 사용할때에는 편리하긴 할텐데, 방향성을 고려 안해도 되는 알고리즘을 쓸때는 불필요한 작업이 될수도 있다. 여기에서는 방향성은 굳이 강제시키지 않는쪽으로 처리했다.
  * 다른곳에서 쓰는 것을 본적이 없긴 하지만.. 꼭지점들을 저장하는 대신에, 변에 해당하는 벡터들을 저장하는 방식도 일리가 있을것 같다. 실제로많은 다각형 관련 알고리즘들(둘레, 면적, 다각형 내부의 점 판별 등등) 은 꼭지점들이 아니라 변들을 갖고서 계산하게 되고, 그래서 항상 인접한 꼭지점들로부터 변 벡터들을 계산해주는 작업을 필요로 한다. 차라리 애초에 변을 저장해놓으면 그런 작업을 피할수 있다!
    * 이론적으로는 일리가 있지만, 신경쓰이는 것은 이런식으로 사용하는 기존 라이브러리를 전혀 본적이 없다는 것. 헷갈릴 때가 종종 있을것 같은것이 첫번째 걱정거리. 
    * 또 하나의 단점은, 변 벡터로 다각형을 표현하려면, 여기에 추가로 시작점의 좌표를 같이 들고 다녀야 한다. 이것도 좀 번거로울때가 있을것 같다
    * 그래서 결국 이 아이디어는 기각하기로.
  * 꼭짓점을 이터레이션 하는 경우보다, 변을 이터레이션 해야하는 경우가 더 많다. 이것을 깔끔하게 코드로 옮기는 방법이 없어서 좀 고민했는데, 결국은 항상 이런식으로 쓰기로 결정했다
    * <dkpr py>
for p1, p2 in itertools.pairwise([*polygon, polygon[0]])
    ...
</dkpr>
    * polygon + [polygon[0]] 대신에 [*polygon, polygon[0]]을 쓰는 이유는, polygon이 list가 아닐 경우까지 고려했기 때문이다. polygon이 + 연산이 정의되어 있지 않은 Sequence 타입일수도 있으니..
    * 더 빠른 것은 itertools.chain(polygon, [polygon[0]]) 으로 쓰는 것이긴 하다. 하지만 itertools.pairwise(itertools.chain(polygon, [polygon[0]])) 이렇게되면 너무 길어져서 예쁘지가 않고 눈에도 잘 안들어온다 ㅜ. 어차피 이렇게 써서 얻는 속도 향상은 거의 미미하다.
      * itertools.chain(itertools.pairwise(polygon), [(polygon[-1], polygon[0])]) 이것도 마찬가지 이유로 기각.
    * 인덱스로 접근하는 것은 속도와 가독성 둘다 안좋지만, 혹시 꼭 인덱스를 써야 할 경우에는 이렇게 쓰면 되기는 한다
      * <dkpr py>
for i in range(len(polygon)):
    p1, p2 = polygon[i - 1], polygon[i]
    ...
</dkpr> 
      * i-1과 i를 쓰는 것이, i와 (i+1)%n 을 쓰는것보다 당연히 효율적
 


===== 볼록 다각형 (Convex Polygon) =====
  * 엄밀한 정의는 다각형 위의 어떤 두 점을 잡아서 선분을 그려도 그 선분이 다각형 내부에 있으면 그 다각형을 볼록다각형이라고 한다.
  * 하지만 이외에도 볼록다각형을 의미하는 다른 표현들이 많이 있다. 문제에서 다른 방식으로 주어져도 볼록다각형을 말하는 것으로 알아들으면 된다.
    * 모든 내각이 180이내인 단순 다각형
    * 다각형을 가로지르는 모든 선들이 다각형과 교점을 2개 갖는다

==== 성질 ====
  * 볼록 다각형 2개가 겹쳐서 만들어지는 영역은 역시 볼록다각형이다.

===== 다각형의 넓이 =====
<WRAP box round>
- 난이도: 골드5 \\
- 기본 문제: [[ps:problems:boj:2166]] \\
- 필요한 사전 지식: [[ps:이론:기초 계산기하#삼각형의 넓이]]
</WRAP>
  * 신발끈 공식 (Shoelace formula) 를 사용해서 꼭짓점의 좌표들로부터 다각형의 면적을 O(n)에 구할 수 있다.
    * 좌푯값을 교차해서 곱하는 모습이 신발끈 묶을 때와 같아서 이러한 이름이 붙었다
    * 가우스의 면적 공식 (Gauss's area formula)이라고도 불린다
  * 참고
    * [[wp>Shoelace formula]]
    * [[https://cp-algorithms.com/geometry/area-of-simple-polygon.html#method-1]]
  * 면적을 계산하는 식은 다음과 같다.
    * $ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}(x_{i}y_{i+1}-x_{i+1}y_{i})} $
      * A의 값은, 꼭짓점들이 반시계 방향으로 정렬되어있으면 양수로, 시계방향으로 정렬되어있으면 음수로 나온다. 그냥 절댓값을 씌우면 면적이 된다.
      * 볼록다각형이 아니더라도 적용된다.
  * 이 식은 다각형을 삼각형들로 분할한 뒤에, 각각의 [[ps:이론:기초 계산기하#삼각형의 넓이]] 를 구해서 합치는 것을 식을 잘 정리하면 유도된다.
  * 신발끈 모양으로 만들어지는 이 형태의 식이 기억하기에는 가장 쉽긴 하지만, 이 식을 다시 변형해서 다른 형태로 표현할수도 있다. 그리고 코드로 작성할 때에는 아래의 형태의 식을 사용하는 편이 곱셈연산의 갯수를 줄일 수 있기 때문에 살짝 더 빠르다.
    * $ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}(y_{i}+y_{i+1})(x_{i}-x_{i+1})} $
      * 사다리꼴의 합으로 계산하는 형태이다
    * $ {\displaystyle A={\frac {1}{2}}\sum _{i=1}^{n}x_{i}(y_{i+1}-y_{i-1})} $
      * 그린 정리의 특수 케이스로 유도되는 형태

==== 구현 ==== 
  * 사다리꼴의 합으로 표현되는 형태의 공식을 사용했다.
  * 다각형의 면적 대신에 면적에 2를 곱한 값을 리턴하도록 했다. 면적은 0.5단위로 나오기 때문에, 면적에 2를 곱한 값을 리턴하면 항상 정수로 리턴할수 있다.
  * <dkpr py>
def twice_of_polygon_area(polygon: Polygon) -> int:
    signed_area = sum(
        (p1[0] - p2[0]) * (p1[1] + p2[1])
        for p1, p2 in itertools.pairwise([*polygon, polygon[0]])
    )
    return abs(signed_area)
</dkpr>
    * [[ps:teflib:geometry#twice_of_polygon_area|teflib.geometry.twice_of_polygon_area]] 에 구현된 버전

==== 관련 문제 ====
  * [[ps:problems:boj:2166]]: 기본 문제


===== 다각형 내부의 격자점의 갯수 =====
<WRAP box round>
- 난이도: 실버2 \\
- 기본 문제: [[ps:problems:boj:27123]]
</WRAP>
  * 픽의 정리 (Pick's theorem) 를 사용하면, 다각형의 넓이로부터 다각형 내부의 격자점의 갯수를 구할 수 있다.
  * 참고
    * [[wp>Pick's theorem]]
    * [[https://cp-algorithms.com/geometry/picks-theorem.html]]
  * 꼭지점이 모두 격자점 위에 있는 단순다각형에 대해서, 다음 공식이 성립한다
    * $ S = I + B / 2 - 1 $
    * S는 다각형의 넓이, I는 다각형 내부에 있는 격자점의 갯수, B는 다각형의 테두리 위에 있는 격자점의 갯수.
  * 수학시간에 배울때는 격자점의 갯수를 세는 것으로 간단하게 넓이를 구할수 있는 방법이라는 관점으로 배우지만, PS에서는 반대로 넓이로부터 내부 격자점의 갯수를 구하는데에 주로 사용된다.
    * 넓이는 [[#다각형의 넓이]]에서 설명한 방식을 이용해서 간단히 계산 가능하다
    * 다각형의 테두리 위에 있는 격자점의 갯수는, 각 변마다 그위에 있는 격자점의 갯수를 구해서 더하면 된다. (x0,y0)-(x1,y1) 위에 있는 격자점의 갯수는 gcd(x0-x1, y0-y1)+1 로 구할 수 있다.
    * 시간복잡도는 n개의 변에 대해 GCD연산을 해줘야 하므로, O(n*log(m)) 이다. (m은 좌표값의 범위)

==== 구현 ==== 
  * 코드
    * [[ps:teflib:geometry#lattice_point_in_polygon|teflib.geometry.lattice_point_in_polygon]]
  * 다각형을 입력받아서 내부 격자점와 테두리 격자점의 갯수를 리턴하는 형태의 함수로 만들었다.
  * 중간 과정에서 다각형의 면적을 계산하지만 그 값은 리턴파지 않는다.
  * 변 위에 있는 격자점의 갯수를 구할때, 변이 축에 수평이나 수직인 경우에는, gcd(0, n)을 계산해야 하므로, 이 경우는 따로 처리해야 할 것 같지만, python의 math.gcd 함수는 gcd(0,n)=n 으로 계산한다. 이 값은 우리가 원하는 값과 같으므로 따로 예외처리를 해줄 필요가 없다.

==== 관련 문제 ====
    * [[ps:problems:boj:27123]]: 기본 문제. 밑변이 x축위에 놓인 삼각형에 대해서, 내부 격자점의 갯수를 구하는 문제. [[#다각형의 넓이]]를 구하는 공식을 사용하지 않고도, 간단히 넓이를 구할 수 있다.


===== 다각형 내부의 점 판별 (Point in polygon; PIP) =====
<WRAP box round>
- 난이도: 플래티넘 5 \\
- 관련 솔브닥 태그: [[https://www.acmicpc.net/problemset?sort=ac_desc&algo=57|오목 다각형 내부의 점 판정]]
- 기본 문제: [[ps:problems:boj:1688]] \\
- 필요한 사전 지식: [[ps:이론:선분 교차]]
</WRAP>
  * 참고
    * [[wp>Point in polygon]]
  * 어떤 점이 다각형 내부에 있는지 외부에 있는지를 판별하는 문제. Point-in-polygon (PIP) 문제라고 불린다.
  * 크게 Ray casting algorithm과, Winding number algorithm 방법이 쓰인다고 한다. 
  * 하지만, Winding number algorithm 은 원래 삼각함수의 역함수로 각도를 계산해서 사용하는 방식이었으나, 그 이후로 개선되어서 현재의 동작방식은 Ray casting algorithm과 거의 비슷한 것 같다. [[https://en.wikipedia.org/wiki/Point_in_polygon#Winding_number_algorithm|위키]]의 설명에서 이해한 바로는, 단순 다각형의 경우에는 Ray casting algorithm과 차이가 없다고 생각해도 무방할 것 같다.
  * 그래서 여기서는 Ray casting algorithm 만 다루기로 하겠다. 시간복잡도는 O(n)이다.
  * 만약 다각형이 볼록다각형이라는 전제가 주어지면, 더 빠르게 내부 판별을 할수 있다. [[#볼록다각형 내부의 점 판별]] 참고.

==== Ray casting algorithm ====
  * 참고
    * [[https://anz1217.tistory.com/107]]
  * 원리는 간단하다. 테스트할 점에서 출발하는 반직선을 만들고, 그 반직선과 교차하는 변의 갯수를 센다. 교차하는 변의 갯수가 홀수개이면, 점이 다각형 내부에 있는 것이고, 짝수개이면 외부에 있는 것이다.
    * 자세한 설명은 위의 링크를 참고.
  * n개의 변에 대해서 교차 여부를 계산해야 하므로 시간복잡도는 O(n)
  * 구현
    * 점 p=(px,py)에서 x축 방향으로 뻗어있는 반직선과 q1과 q2를 잇는 선분의 교차 여부는, p2=(inf, py) 점을 잡고 p1-p2선분과 q1-q2선분사이의 교차 여부를 찾는 것으로 바꿔 쓰면, [[ps:이론:선분 교차]]에서 작성한 코드를 그대로 사용할 수도 있기는 하다. 하지만, 선분 교차 판별은 4번의 방향관계 연산을 사용하고, 이는 상당히 비효율적이다. 
    * 깔끔한 것은, q1y 와 q2y 가 py 기준으로 반대 방향에 있는지를 확인하고, 만약 그렇다면, q1, q2, p 점 간의 방향관계만을 확인해서 처리하는 것이다. q1y < q2y 일때, 반직선과 선분이 교차하기 위해서는 q1, q2, p가 반시계방향으로 위치해야만 한다.
    * 또한, 반직선과 선분이 겹치는 경우와 반직선이 선분의 끝점을 지나는 경우에 대한 예외처리가 필요하다.
      * 반직선과 선분이 겹치는 경우는 교차하지 않는 것으로 카운팅해줘야 한다
      * 반직선이 선분의 끝점을 지나는 경우는, 실제로는 반직선이 다각형의 꼭짓점을 지나는 경우이고, 이 경우는 두개의 선분의 끝점을 지나가지만 한개의 선분과만 교차하는 것으로 카운팅해줘야 한다.
        * q1y < q2y == py 일때에는 교차하는 것으로, py == q1y < q2y 일 경우에는 교차하지 않는 것으로 처리하면 한개의 선분에 대해서만 카운팅해 줄 수 있다.
    * 실제 구현은, x축 방향으로 뻗은 반직선 대신에, y축 방향으로 뻗은 반직선을 이용했다. 그 편이 좀 더 코드가 깔끔하게 짜여졌다.
    * 내부와 외부뿐 아니라, 변 위에 점이 존재하는 경우도 따로 구분하도록 함수를 만들었다.
  * 코드
    * [[ps:teflib:geometry#polygon_and_point_relation|teflib.geometry.polygon_and_point_relation]]

==== 관련 문제 ====
  * [[ps:problems:boj:1688]]


===== 볼록다각형 내부의 점 판별 =====

==== 볼록껍질 내부의 점 판별 ====
  * 점들 p1, p2, ..., pn으로 만들어지는 볼록 껍질 안에 점 q가 존재하는지 여부를 물어보는 경우가 있다.
  * 직관적인 방법은 pi들로부터 볼록 껍질을 만들 다음에, q가 그 볼록껍질 안에 있는지를 [[#볼록 다각형 내부의 점 판별]] 방법으로 찾는 것이다.
  * 하지만, 조금 더 간단하게 처리할수도 있다. pi들로 부터 볼록 껍질을 만드는 대신에 pi들과 q로부터 볼록 껍질을 만드는 것이다. pi로 만들어졌을 볼록껍질을 H, pi들과 q로부터 만들어지는 볼록껍질을 H'이라고 하자. 이렇게 H대신 H'을 만든 다음, q와 H'과의 관계로부터 q와 H와의 관계를 파악할수 있다.
    * 만약 q가 H'의 꼭짓점 중 하나라면, q는 H의 외부에 있다.
    * 만약 q가 H'의 변 위에 있다면, q는 H의 변 위에 있다.
    * 그 외에 경우에는, q는 H의 내부에 있다. 


===== 단순 다각형 여부 판별 =====
  * 다각형이 단순 다각형(simple polygon)인지는 교차하는 변이 존재하는지 여부를 확인하면 알수 있다.
  * 각 변을 그냥 선분들이라고 생각하면, 샤모스-호이 알고리즘을 이용해서 O(nlogn)에 확인 가능하다.
    * [[ps:이론:선분 교차#교차하는 선분의 존재 여부 확인]] 참고