다각형

다각형은 어떤 닫힌 꺾은선으로 둘러싸인 평면의 일부로 정의됩니다.

다각형의 경계 꺾은선에 자기 교차점이 없으면 그 다각형을 단순 다각형이라고 합니다. 그림에서 마지막 다각형을 제외한 모든 다각형은 단순 다각형입니다.

다각형의 임의의 두 점에 대해 그 두 점을 잇는 선분 위의 모든 점도 다각형에 속하면, 그 다각형을 볼록하다고 합니다. 처음 두 다각형은 볼록합니다.

볼록 다각형의 모든 변과 모든 각이 같으면 그 다각형을 정다각형이라고 합니다. 모든 정다각형은 원에 내접시킬 수도 있지만, 그 역은 성립하지 않습니다.

3차원 공간에서 다각형을 일반화한 것은 다면체입니다.

#넓이

가장 간단한 경우인 삼각형의 경우에는 밑변과 높이를 이용한 기존 공식으로 넓이를 구할 수도 있고, 벡터곱의 성질을 이용할 수도 있습니다:

순회 순서대로 나열된 꼭짓점의 수열로 주어진 임의의 다각형의 경우에는 다음과 같이 할 수 있습니다. 모든 변을 순회하면서, 각 변에 대해 그 변과 원점으로 정해지는 삼각형의 유향 넓이를 합에 더합니다.

그림의 예에서 넓이는 다음과 같은 벡터곱의 합과 같습니다:

시계 방향으로 이어지는 모든 꼭짓점 쌍은 음의 부호로, 반시계 방향으로 이어지는 쌍은 양의 부호로 계산되므로 불필요한 넓이가 상쇄됩니다.

이 공식은 자기 교차가 없는 모든 다각형에 대해, 심지어 볼록하지 않은 다각형에 대해서도 성립합니다. 이를 확인하려면 평면 위의 임의의 점 하나를 고정하고, 그 점이 합에서 몇 번, 어떤 부호로 계산되는지 확인해 보십시오.

최종 결과의 부호는 다각형을 어떤 순서로 순회하는지에 따라 달라진다는 점에 유의하십시오(이를 신경 쓰지 않으려면 결과에 절댓값을 취하면 됩니다).

double area(vector<r> p) {
    int n = (int) p.size();
    double s = 0;
    for (int i = 0; i < n; i++)
        s += p[i] ^ p[(i + 1) % n];
    return abs(s) / 2;
}

또한 어쩌면 더 직관적이지만 더 번거로운 사다리꼴 방법도 있습니다. 이 방법에서도 마찬가지로 모든 변을 순회하며 부호 있는 넓이를 더하지만, 원점을 기준으로 한 삼각형이 아니라 $x$축 위에 밑변을 둔 사다리꼴의 넓이를 더하며, 이때 “아래쪽” 사다리꼴이 마찬가지로 “위쪽” 사다리꼴의 남는 넓이를 상쇄합니다.

넓이를 계산하는 방법과 관계없이, 삼각형 넓이 공식으로부터 모든 좌표가 정수이면 임의의 도형의 넓이는 정수이거나 분모가 2인 유리수가 된다는 점에 주목합시다. 문제에서는 입력 데이터가 모두 정수인 경우가 많은데, 정수 범위에서 계산하기 위해 모든 입력 수에 $2$를 곱하는 것이 때때로 유용합니다. 그러면 모든 넓이가 정수가 됩니다(게다가 짝수가 됩니다).

#점의 포함 여부

이번에도 삼각형부터 시작합시다. 점 $P$가 반시계 방향으로 주어진 삼각형 $ABC$ 안에 있는지 판별해야 합니다. 그러면 점은 세 선분 $AB$, $BC$, $CA$ 모두의 왼쪽에 있어야 합니다. 이 조건은 세 반평면의 교집합을 정의하며, 이 교집합이 바로 원하는 삼각형이 됩니다.

이와 같은 검사는 볼록 다각형의 경우로 일반화할 수 있습니다. 이를 위해서는 꼭짓점을 반시계 방향으로 순회하면서 점 $P$가 모든 변의 “왼쪽"에 있는지 확인하면 됩니다.

다각형이 볼록한지 확인하려면 다각형의 변을 따라가면서 벡터곱으로 우리가 항상 한쪽 방향으로만 «회전»하는지 확인하면 됩니다. 즉, 모든 연속한 점 $a$, $b$, $c$에 대해 $(b-a)\times(c-a) > 0$인지 확인합니다.

다각형이 고정되어 있고 포함 여부를 확인하는 쿼리가 들어오는 문제 설정에서는 선형 시간보다 더 빠르게 해결할 수 있습니다.

#임의의 다각형

더 일반적인 경우에는 널리 쓰이는 두 가지 방법이 있으며, 둘 다 $O(n)$에 동작합니다.

첫 번째 방법은 각도를 세는 것입니다. 순회 순서대로 모든 꼭짓점을 차례로 거치면서, 점 $P$를 꼭짓점으로 하고 다각형의 이웃한 두 꼭짓점을 지나는 반직선들로 이루어진 각을 순서대로 살펴봅시다. 이 유향 각들을 모두 더하면 어떤 값 $\theta$가 나옵니다. 점 $P$가 다각형 내부에 있으면 $\theta = \pm 2 \pi$이고, 그렇지 않으면 $\theta = 0$입니다.

두 번째 방법은 $P$에서 쏜 반직선이 다각형의 변과 몇 번 교차하는지를 세는 것입니다.

임의의 점에서 아무 반직선이나 쏘았을 때 이 반직선이 다각형과 교차한다면, 반직선은 언젠가는 반드시 그 다각형 밖으로 나가게 됩니다. 반직선은 무한하지만 다각형은 그렇지 않기 때문입니다.

다각형과의 교차 횟수를 세어 보면, 내부에 있는 점의 경우 이 횟수는 홀수가 되고(«바깥-안-바깥», 교차 3번), 그렇지 않은 경우에는 짝수가 됩니다.

반직선이 꼭짓점을 지나는 경우(한 번에 2개의 변과 교차하는 경우)를 따로 처리하지 않으려면 반직선의 방향을 무작위로 정하면 됩니다. 실수값으로 주어지는 방향이 유한 개의 점 중 하나와 일치할 확률은 무시할 수 있을 만큼 작습니다.