Geometry(Polygon)

Feb 25, 2019

  • Convex Polygon(볼록 다각형) : 모든 내각이 180도 미만인 다각형

  • Concave Polygon(오목 다각형) : 180도가 넘는 내각을 갖는 다각형

  • Simple Polygon(단순 다각형) : 다각형의 경계가 스스로 교차하지 않는 다각형

  • 성질

    • 볼록 다각형 내부의 임의의 두 점을 연결하는 선분은 볼록 다각형의 테두리를 절대 교차하지 않는다.
    • 두 볼록 다각형의 교집합은 항상 볼록 다각형이다. (없을수도..?)

  • 일반적인 다각형의 구현은 다각형의 꼭지점들을 나타내는 리스트로 표현된다. (P0, P1, …, Pn-1)

  • 볼록 다각형의 면적 구하기

    • 다각형 P를 n개의 꼭지점으로 표현하는데 이를 반시계 방향으로 나열(정렬)한다.
    • 다각형 내부의 한 점(q)을 잡고 그 점과 인접한 두 정점({P0, P1}, {P1, P2}, …, {Pn-2, Pn-1}, {Pn-1, P0})들로 이루어진 삼각형들로 분리한 뒤 벡터의 외적을 이용한다.

  • 오목 다각형의 면적 구하기

    • 볼록 다각형과 다른 점은 평면 상의 한 점(q)을 잡는다는 점 뿐이다.
    • 마찬가지로 인접한 두 정점들로 이루어진 삼각형들의 면적을 구하게 되면 좌회전할 때는 양수이고 우회전할 때는 음수가 나오므로 그대로 다 더해주면 다각형에 속하지 않는 면적들은 자연스레 빠지게 된다.
  • double area(Polygon p, int n) {
    double ret = 0;
    for(int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        ret += p[i].x * p[j].y - p[i].y * p[j].x;
    }
    return abs(ret) / 2;
}

    다각형 포함 문제 : 다각형 P와 점 q가 주어졌을 때, q가 P의 내부에 위치하고 있는지 여부를 검사

    • 잘 분석해보면 점 q에서 뻗어나오는 반직선을 R이라고 할 때, R과 P의 경계선과의 교차점 수에 따라 판별할 수 있다는 것을 알 수 있다.
    • 홀수이면 q는 P의 내부, 짝수이면 외부
    • 그러나 예외가 존재, 반직선 R이 꼭지점 혹은 경계선에 접해서 지나는 경우가 있다.
    • 이를 해결하는 방안은 반직선 R과 교차하는 경계선에 대해서, 경계선의 한 쪽 끝점이 R에 위치하는지를 판단하고 R에 위치해 있다면 경계선의 반대쪽 끝점이 R을 기준으로 반대편에 있는지를 확인해야 한다.
    • 예외 2 : 점 q가 P의 경계선 위에 존재하는가? 먼저 점 q가 P의 각 경계선 위에 위치하는지 검사하면 해결
    bool insidePolygon(Point q, Polygon P, int n) {
    int c = 0;
    Point ori = {0, 0};
    // 점 q가 원점에 오도록, 반직선은 양의 x축이 된다.
    for(int i = 0; i < n - 1; i++) P[i].x -= q.x, P[i].y -= q.y;
    for(int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        if (between(P[i], P[j], ori)) return 0;
        if (P[i].y < 0 && P[j].y >= 0 && ccw(P[i], P[j], ori) == 1 || P[j].y < 0 && P[i].y >= 0 && ccw(P[j], P[i], ori) == 1) c++;
    }
}