[C++ 알고리즘] 다각형 내부의 점 판정 알고리즘 (Point in Convex Polygon)

이 포스트에서는 다각형 내부의 점 판정 알고리즘에 대한 예시 코드와, 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac 기준 'Point in Convex Polygon' 태그의 문제들에 대한 풀이 코드와 해설을 다룹니다.

 

 

 

최근 기하 문제들을 많이 풀이하고 있는데, Convex Hull 알고리즘과 Roating Calipers 알고리즘만으로는 해결할 수 없는 문제들이 있습니다.

이들 중 가장 자주 보이는 태그 중 하나는 point_in_convex_polygon으로, 다각형 내부의 점 판정을 하는 알고리즘입니다.

따라서 이번 포스트에서는 위의 문제들을 해결할 수 있는 다각형 내의 점 판정 알고리즘을 구현해보고, 나아가 예제 하나를 풀이해보도록 하겠습니다.

 

문제는 가장 쉬운 문제를 풀이를 하면서 일반화시켜서 구현된 알고리즘을 적용시켜볼 것입니다.

 

 

2987번 : 사과나무

 

삼각형의 세 꼭짓점의 좌표와, N개의 점들이 주어졌을 때 삼각형의 넓이와 삼각형의 경계를 포함한 내부의 점들이 몇 개인지 Count하는 문제입니다.

다각형 중에서 가장 꼭짓점의 수가 적은 도형이 삼각형이므로, 이 문제는 위의 알고리즘 중에서 가장 간단한 형태의 문제임을 알 수 있습니다.

그렇다면 어떻게 점 판정을 할 수 있는지 구현해보도록 하겠습니다.

 

** 참고로 삼각형 내부의 점 판정은 간단히 CCW 몇 번만 사용해도 판정이 가능하지만, 여기서는 뒤의 더 어려운 문제들까지 해결할 수 있도록 다각형이 Size각형이라는 가정 하에 문제를 풀이해보도록 하겠습니다.

 

 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define N 3
using namespace std;

struct Point { int x, y; };
Point operator-(Point A, Point B) {
    Point C;
    C.x = A.x - B.x, C.y = A.y - B.y;
    return C;
}
vector<Point> Poly;

int Abs(int A) { return A>=0?A:-A; }

int Cross(Point A, Point B, Point C) {
    Point AB = B-A;
    Point AC = C-A;
    return AB.x*AC.y - AB.y*AC.x;
}

bool CompareCross(Point A, Point B) {
    int Value = Cross(Poly[0], A, B);
    if(Value) return Value > 0;
    else if(A.y != B.y) return A.y < B.y;
    else return A.x < B.x;
}

bool isInPoly(vector<Point> &Poly, Point P) {
    int Size = Poly.size();
    Point Origin; Origin.x = 0, Origin.y = 0;
    Point LeftV = Poly[Size-1] - Poly[0];
    Point RightV = Poly[1] - Poly[0];
    Point PointV = P - Poly[0];
    if(Cross(Origin, LeftV, PointV) > 0) return false;
    if(Cross(Origin, RightV, PointV) < 0) return false;

    int Left = 1, Right = Size - 1;
    while(Left+1 < Right) {
        int Mid = (Left + Right)/2;
        Point MidV = Poly[Mid] - Poly[0];
        if(Cross(Origin, MidV, PointV) > 0) Left = Mid;
        else Right = Mid;
    }
    Point V1 = P - Poly[Left];
    Point V2 = Poly[Left+1] - P;
    return Cross(Origin, V1, V2) <= 0;
}

int main() {
    Poly.resize(N);
    for(int i=0; i<N; i++) scanf("%d %d", &Poly[i].x, &Poly[i].y);
    for(int i=1; i<N; i++)
        if(Poly[i].y < Poly[0].y || (Poly[i].y == Poly[0].y && Poly[i].x < Poly[0].x))
            swap(Poly[0], Poly[i]);
    sort(Poly.begin()+1, Poly.end(), CompareCross);

    stack<Point> Convex;
    Convex.push(Poly[0]);
    Convex.push(Poly[1]);
    for(int i=2; i<N; i++) {
        while(Convex.size() >= 2) {
            Point Temp2 = Convex.top();
            Convex.pop();
            Point Temp1 = Convex.top();
            if(Cross(Temp1, Temp2, Poly[i]) > 0) {
                Convex.push(Temp2);
                break;
            }
        }
        Convex.push(Poly[i]);
    }
    vector<Point> SortedPoly;
    int Size = Convex.size();
    SortedPoly.resize(Size);
    for(int i=Size-1; i>=0; i--) {
        SortedPoly[i] = Convex.top();
        Convex.pop();
    }

    int M, Cnt = 0;
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        Point P;
        int x, y;
        scanf("%d %d", &x, &y);
        P.x = x, P.y = y;
        if(isInPoly(SortedPoly, P)) Cnt++;
    }
    printf("%.1lf\n", (double)Abs(Cross(SortedPoly[0], SortedPoly[1], SortedPoly[2]))*0.5);
    printf("%d", Cnt);
}

 

코드가 무지막지하게 길어져버렸는데, isInPoly 함수가 판정의 핵심이고, 나머지는 Convex Hull 알고리즘을 그대로 갖다 쓴 것입니다.

기하이다보니 말로만 설명하기에는 부족한 감이 있어 isInPoly 함수의 작동 원리를 그림으로 설명하겠습니다.

 

 

 

먼저 Poly[0]을 기준점으로 잡고, 이를 기준으로 반시계 순으로 가장 오른쪽에 있는 벡터를 RightV, 가장 왼쪽에 있는 벡터를 LeftV로 잡아줍니다.

가장 먼저 LeftV와 RightV 사이의 내부각에 들어오지 않는 점들을 배제시켜줍니다. (ccw 알고리즘으로 판정 가능)

그 다음, 각 벡터 사이의 section을 구분짓고 이분 탐색을 통해 P가 어느 section에 포함되어 있는지를 찾습니다. (이 때도 여전히 P는 다각형의 밖에 위치할 수 있습니다. 어떤 각에 포함되어 있는지 그 영역을 찾는 것입니다.)

마지막으로 P와 찾은 section 변 사이의 위치 관계를 확인해주면 됩니다. (이 역시 ccw 알고리즘으로 판정 가능)

 

 

 

제출해보면 거의 시간이 소요되지 않고 CA 처리를 받을 수 있습니다.

이 문제는 삼각형이기에 일반화된 알고리즘이 필요 없지만, 다음 포스트에서 이 알고리즘을 활용하여 더욱 일반화된 문제를 풀이해보도록 하겠습니다.