Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 볼록 다각형(Convex Polygon) 판별하기

순서대로 연결했을 때 하나의 다각형을 이루는 점들의 목록이 주어졌을 때, 이 다각형이 볼록 다각형(convex polygon)인지 판별하는 문제입니다. 이때 점의 개수는 최소 3개에서 최대 10,000개이며, 각 좌표 값은 -10,000부터 10,000 사이의 범위에 있다는 조건이 주어집니다.

주어진 점들로 형성되는 다각형은 항상 단순 다각형(simple polygon)이라고 가정할 수 있습니다. 즉, 각 꼭짓점에서 정확히 두 개의 변이 만나고, 그 외의 경우에는 변들이 서로 교차하지 않는다는 것이 보장됩니다. 예를 들어 입력이 [[0,0],[0,1],[1,1],[1,0]]이라면 이 다각형은 볼록하므로 결과값으로 true를 반환하게 됩니다.

해결 접근 방법

이 문제는 벡터의 외적(cross product)을 이용해 해결할 수 있습니다. 외적의 부호는 두 벡터의 회전 방향을 나타내는데, 볼록 다각형에서는 모든 꼭짓점에서의 회전 방향이 일관되게 유지되어야 하기 때문입니다. 구체적인 풀이 단계는 다음과 같습니다.

  • calc() 메서드를 정의합니다. 이 메서드는 ax, ay, bx, by, cx, cy 여섯 개의 값을 받아 다음과 같이 동작합니다.
  • BAx := ax − bx, BAy := ay − by, BCx := cx − bx, BCy := cy − by 를 계산한 뒤, 두 벡터의 외적인 (BAx × BCy − BAy × BCx) 값을 반환합니다.
  • 메인 메서드에서는 neg와 pos를 false로 초기화하고, n을 점 배열의 크기로 설정합니다.
  • i를 0부터 n − 1까지 반복하며 다음을 수행합니다.
    • a := i, b := (i + 1) mod n, c := (i + 2) mod n 으로 설정합니다.
    • cross_prod := calc(p[a][0], p[a][1], p[b][0], p[b][1], p[c][0], p[c][1]) 을 계산합니다.
    • cross_prod가 0보다 작으면 neg를 true로, 0보다 크면 pos를 true로 설정합니다.
    • neg와 pos가 모두 true라면 회전 방향이 뒤섞인 것이므로 false를 반환합니다.
  • 모든 반복을 마치고 방향이 일관되었다면 true를 반환합니다.

C++ 코드 예제

아래 구현을 살펴보면 더 쉽게 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool isConvex(vector<vector<int>>& points) {
        bool neg = false;
        bool pos = false;
        int n = points.size();
        for(int i = 0; i < n; i++){
            int a = i;
            int b = (i + 1) % n;
            int c = (i + 2) % n;
            int crossProduct = calc(points[a][0], points[a][1], points[b][0], points[b][1], points[c][0], points[c][1]);
            if(crossProduct < 0) neg = true;
            else if(crossProduct > 0) pos = true;
            if(neg && pos) return false;
        }
        return true;
    }
    int calc(int ax, int ay, int bx, int by, int cx, int cy){
        int BAx = ax - bx;
        int BAy = ay - by;
        int BCx = cx - bx;
        int BCy = cy - by;
        return (BAx * BCy - BAy * BCx);
    }
};
main(){
    vector<vector<int>> v = {{0,0},{0,1},{1,1},{1,0}};
    Solution ob;
    cout << (ob.isConvex(v));
}

입력

[[0,0],[0,1],[1,1],[1,0]]

출력

1