Geometric Algorithm 정리

Geometric Algorithm 정리

Sep 7, 2024

algorithm
geometry

Geometric Algorithm 정리

제목	날짜
Counter Clock Wise	23.10.25
선분-교차-판정 (line-crossing)	23.10.25
Convex hull	23.10.25
다각형 내부 점 판별	23.10.25
다각형 넓이	23.10.25

Counter Clock Wise (CCW)

CCW란 두 벡터가 시계방향인지, 반시계 방향인지 판별하는 방법이다.

시계 방향 : 음수
반시게 방향 : 양수
일직선 : 0

CCW는 기본적으로 외적으로 계산이 된다.

int64_t cross(const Point &p, const Point &q){
    return p.X*q.Y - q.X*p.Y;
}

int64_t ccw(Point p, Point q, Point r){
    int64_t c = cross(q-p, r-q);
    if(c > 0) return 1;
    else if(c == 0) return c;
    else return -1;
}

선분 교차 판정 (Line Crossing)

선분 교차 판정은 CCW 를 이용할 수 있다.

case 1)

점 $a,b,c,d$ 가 있을 때 선분 $ab$ 와 선분 $cd$ 가 교차하는 경우이다. 이때는 두 선분에 대해 나머지 두점의 CCW의 곱이 음수가 나와야한다.

즉 $CCW(a,b,c)* CCW(a,b,d) < 0\quad \&\& \quad CCW(c,d,a) * CCW(c,d,b) < 0$ 을 만족해야한다.

case 2 )

4개의 점중 선분 $ab$ 위에 점 $c$ 또는 점 $d$ 가 있거나 그 반대의 경우이다. 이때는 선분 위에 있는 점은 CCW가 0이 되지만, 다른 선분에 대해서는 CCW의 곱이 음수가 나와야한다.

$CCW(a,b,c)* CCW(a,b,d) <= 0\quad \&\& \quad CCW(c,d,a) * CCW(c,d,b) <= 0$

을 만족해야한다.

case 3 )

4개의 점이 일직선 위에 있으면서 겹치는 경우이다. 이 경우엔 CCW 를 해도 모두 0이 나오게 되어, 각 점에 대해서 위치를 비교해야한다. 이때 전처리가 필요하다.

$a > b → swap(a,b)$
$c > d → swap(c,d)$

이후 점들에 대해서 비교를 해야한다.

$c≤b \quad \&\& \quad a ≤d$ 를 만족해야한다.

이를 코드로 정리하면 다음과 같다.

bool Cross(Point a, Point b, Point c, Point d){
    int ab = CCW(a,b,c) * CCW(a,b,d);
    int cd = CCW(c,d,a) * CCW(c,d,b);
    
    if(ab == 0 && cd == 0){
        if(a > b) swap(a,b);
        if(c> d) swap (c,d);
        return b >= c && a <= d;
    }
    return ab <= 0 && cd <= 0;
}

선분의 교점 구하기

선분이 만약 교차한다면 선분이 두점 이상 겹치는 경우나, 만나지 않는 경우를 제외하면 교점을 구할 수 있다.

\[(x,y) = ( \frac{(x_1y_1 - y_1x_2)(x_3 - x_4)-(x_1-x_2)(x_3y_4-y_3x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y-2)(x_3-x_4)},\\ \frac{(x_1y_1 - y_1x_2)(y_3 - y_4)-(y_1-y_2)(x_3y_4-y_3x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y-2)(x_3-x_4)})\]

위의 식을 보면 분모가 같은 것을 알 수 있다. 이 분모가 0인 경우에 두 선분이 일직선 위에 있는 경우이고, 이때만 선분의 4점에 대해 위치 파악만 해주면 된다.

Convex Hull

Convex Hull이란 임의의 여러 점이 주어진다면 이 점들을 모두 포함하는 가장 작은 볼록 다각형을 의미한다.

기본적으로는 $O(n^3)$ 을 이용하여 모든 점쌍을 비교할 수 있지만, 이는 효율이 너무 떨어지기 때문에 Graham’s Scan 또는 Andrew’s scan을 사용할 것이다.

Graham’s Scan

x좌표가 가장 작은 점(여러개인 경우 y 가 가장 작은 점) P를 찾는다. 이때 P는 항상 볼록 껍질의 꼭짓점으로 , $O(N)$ 이 걸린다.
다른 모든 점들을 P를 기준으로 각도 순서대로 (일직선이면 가까운 점이 먼저 오도록) 정렬한다.
- 모든 점을 반시계 방향으로 정렬 (CCW)
- $O(N \log N)$ 에 정렬이 가능하다.
점을 차례대로 볼록 껍질에 넣는 방식으로 진행하며 스택으로 관리한다.
1. 처음은 P와 $P_1 , P_2$ 부터 시작한다.
2. 그 다음 점을 보면서 차례대로 밑의 과정을 수행한다.
  1. 스택의 맨 뒤에 있는 점 B, 두번쨰 뒤의 점 A, 현재 점 i
  2. 루프 CCW(A,B,i) ≤ 0 인 경우에 스택에서 B를 제거
  3. i를 스택에 넣는다.

int Dist(Point p1, Point p2){
    int dx = p2.x - p1.x, dy = p2.y -p1.y;
    return dx*dx + dy*dy;
}

vector<Point> ConvexHull(vector<Point> points){
    swap(points[0], *min_element(points.begin(), points.end()));
    sort(points.begin()+1, points.end(), [&](auto a, auto b){
        int d = CCW(points[0],a,b);
        if(d != 0) return d > 0;
        return Dist(points[0],a) < Dist(points[0],b);
    });
    vector<Point> s;
    for(auto i : points){
        while(s.size()>=2 && CCW(s[s.size()-2], s.back(),i) <= 0) s.pop_back();
        s.push_back(i);
    }
    return s;
    
}

Andrew’s Scan

Graham’s scan은 한점을 기준으로 시계 반대방향으로 점들을 정렬후 구했다면 andrew’s scan은 가장 끝의 한점을 시작해서 좌표축 기준으로 정렬한 뒤 구하는 알고리즘이다.

vector <Point> convexHull(vector<Point> &v){
    sort(v.begin(),v.end(),cmp);
    vector <Point> top,bot;
    for(auto i : v){
        while(top.size()>=2 && cross(top[top.size()-1]-top[top.size()-2], i - top[top.size()-1]) >= 0) top.pop_back();
        top.push_back(i);
        while(bot.size()>=2 && cross(bot[bot.size()-1]-bot[bot.size()-2], i - bot[bot.size()-1]) <= 0) bot.pop_back();
        bot.push_back(i);
    }
    vector <Point> rst;
    for(auto i = 0;i+1<bot.size();i++){
        rst.push_back(bot[i]);
    }
    for(auto i = top.size()-1;i>=1;i--){
        rst.push_back(top[i]);
    }
    return rst;
}

다각형 내부 점 판별

기본적인 경우

다각형 내부의 점을 판별하려면 다음을 이용하면 된다.

점에서 시작하는 반직선을 그리고, 다각형과의 교점 개수로 판별
교점이 홀수면 내부
교점이 짝수면 외부

중요한 점은 반직선을 설정해줘야하는데, 임의의 반직선을 설정할 경우에 다각형의 변 또는 꼭짓점에 겹치는 경우가 싱길 수 있다. 이런 경우를 방지하기 위해 반직선을 다음과 같이 처리하면 겹치는 경우가 사라진다.

$(x,y) , (INF, y+1)$ 이렇게 설정하면 기울기가 $1/INF$ 이 되므로, 겹치지 않게 된다. 이 경우 점의 개수를 $N$ 이라 한다면 $O(N)$ 이 걸린다.

bool polygon_check(const vector<Point> &v, Point p1){
    int n = v.size(), cnt = 0;
    
    Point p2(INF+1, p1.y+1);
    for(int i = 0; i<n;i++){
        int j = i+1 == n ? 0 : i+1;
        cnt += Cross(v[i],v[j],p1,p2);
    }
    return cnt & 1;
}

볼록다각형에서의 점 판별

볼록다각형도 다각형의 속하기에 위의 알고리즘을 이용하여 구할 수 있지만 $O(\log N)$ 안에서도 충분히 구할 수 있다.

볼록 다각형은 삼각형으로 분리가 가능하다.

한점을 기준으로 각 꼭짓점에 대한 반직선 긋기
해당 점이 반직선에 대해 왼쪽인지 오른쪽인지 판별 가능 —> CCW
이분 탐색을 이용
마지막에는 삼각형 각 변에 대해 판단을 해주면 된다.

bool ConvexHull_check(vector<Point> &v, const Point &pt){
    if(CCW(v[0],v[1],pt) < 0) return false;
    int l = 1, r = v.size() -1;
    while(l < r){
        int m =( l + r + 1 ) >> 1;
        if(CCW(v[0],v[m],pt) >= 0) l = m;
        else r = m-1;
    }
    if(l == v.size() -1){
        return CCW(v[0], v.back(), pt) == 0 && v[0] <= pt && pt <= v.back();
    }
    return CCW(v[0], v[l],pt) >= 0 && CCW(v[l],v[l+1],pt) >=0 && CCW(v[l+1],v[0],pt) >=0;
}

다각형의 넓이

신발끈 공식

볼록 다각형의 넓이를 구하는 공식으로, 꼭짓점이 반시계 방향일때 적용이 가능하다.

\[ \frac{1}{2}\left| \sum_{i=1}^{n-1} (p_i \times p_{i+1})\right|\]

이때 각 꼭짓점들을 외적을 이용하여 풀어내야하며, $p_n$ 은 $p_1$ 과 같아야 한다.

int64_t shoe_lace(vector<Point> &v){
    
    vector<Point> t = v;
    t.push_back(v[0]);
    
    int64_t sum = 0;
    for(int i = 0; i<t.size()-1;i++){
        sum += cross(t[i], t[i+1]);
    }
    
    return sum >> 1;
}

Jinhuyk Mun