다각형 내부 점 판정

어떤 다각형과 점이 주어질 때, 점이 다각형 내부에 있는지 여부를 판별해 봅시다.

 

다음과 같이 다각형과 점들이 있다고 가정합시다.

각각의 점에서 시작하면서, x축에 평행한 반직선을 그어 봅시다. (반직선의 방향은 상관없습니다)

 

이 반직선이 다각형의 변과 홀수번 교차한다면, 이 점은 다각형 내부에 있습니다.

짝수번 교차한다면, 이 점은 다각형 외부에 있습니다.

 

선분과 반직선의 교차판정은 역시 CCW를 이용하면 편리합니다.

교차 판정시 다음과 같은 예외를 조심합시다.

 

1. 반직선이 다각형의 꼭짓점을 지날 때

꼭짓점 기준 위쪽에 있는 변/아래쪽에 있는 점 중 한가지 경우에만 교차한다고 판정하면 됩니다.

 

2. 반직선이 일부 변을 완전히 포함할 때

이 변과는 교차하지 않는다고 판정하면 됩니다.

 

시간복잡도는 다각형의 모든 변에 대해 교차를 확인하므로, \(O(n)\)입니다. (\(n : \) 다각형의 변의 개수)

 

www.acmicpc.net/problem/1688

1688번: 지민이의 테러

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
pll p2v(pll a, pll b) // 두 점 A,B가 주어지면 벡터 AB를 반환
{
    return { b.first - a.first, b.second - a.second };
}
 
ll ccw(pll v1, pll v2) // 벡터 v1, v2의 CCW
{
    ll res = v1.first * v2.second - v1.second * v2.first;
 
    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}
 
int n;
vector <pll> CH;
 
bool isInside_nonconvex(vector <pll>& CH, pll point)
{
    int cnt = 0;
    for (int i = 0; i < CH.size(); i++)
    {
        // x축에 평행하고 point에서 시작하는 반직선과, 선분 p1 p2가 교차하는지 여부
        pll p1 = CH[i], p2 = CH[(i + 1) % CH.size()];
        if (p1.second < p2.second) swap(p1, p2);
 
        pll v1 = p2v(p1, point);
        pll v2 = p2v(point, p2);
 
        if (ccw(v1, v2) == 0)
        {
            // 일단 점이 선분위에 있는지 확인
            if (min(p1.first, p2.first) <= point.first && point.first <= max(p1.first, p2.first)
                && min(p1.second, p2.second) <= point.second && point.second <= max(p1.second, p2.second))
                return true;
        }
 
        if (max(p1.first, p2.first) < point.first) continue;
        if (p1.second <= point.second) continue; // 1
        if (p2.second > point.second) continue;  // 2 둘 중 하나에만 등호가 들어가야 한다.
        if (min(p1.first, p2.first) > point.first) cnt++;
        else if (ccw(v1, v2) > 0) cnt++;
    }
 
    return cnt % 2;
    // 홀수번 교차하면 다각형 내부이다.
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        ll x, y; cin >> x >> y;
        CH.push_back({ x,y });
    }
 
    for (int i = 0; i < 3; i++)
    {
        ll x, y; cin >> x >> y;
        if (isInside_nonconvex(CH, { x,y })) cout << "1\n";
        else cout << "0\n";
    }
}
 

---

만약 다각형이 볼록다각형이라면, 다각형 내부 판정을 더 빠르게 할 수 있습니다.

 

볼록 다각형의 한 점에서 시작해, 나머지 점들로 이어지는 반직선을 차례대로 그어 봅시다.

 

\(n\)각형에서 어떤 점이 다각형 내부에 위치하기 위해서는, 우선 1번과 \(n-1\)번 반직선 사이에 점이 존재해야 합니다.

두 직선 사이에 점이 존재함을 확인했다면, 반직선으로 만들어지는 \(n-2\)개의 구간 중 어떤 구간에 점이 존재하는지 이분탐색으로 알아낼 수 있습니다.

모든 각 비교는 CCW를 사용하면 편리합니다.

 

 

2번과 3번 반직선 사이에 점이 존재할 때

점이 \(i\)번 반직선과 \(i+1\)번 반직선 사이에 있음을 알아냈다면, 세 점의 방향성을 판단함으로써 다각형 내부 판정을 하면 됩니다.

이 역시 CCW를 이용합니다.

 

시간복잡도는 다각형이 이미 만들어져 있다는 가정하에 \(O(\log n)\)입니다.

 

www.acmicpc.net/problem/20670

20670번: 미스테리 싸인

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
pll p2v(pll a, pll b) // 두 점 A,B가 주어지면 벡터 AB를 반환
{
    return { b.first - a.first, b.second - a.second };
}
 
ll ccw(pll v1, pll v2) // 벡터 v1, v2의 CCW
{
    ll res = v1.first * v2.second - v1.second * v2.first;
 
    if (res > 0) return 1;
    else if (res < 0) return -1;
    else return 0;
}
 
int n, m, k;
vector <pll> CH[2];
 
bool isInside(vector <pll>& CH, pll point)
{
    int n = CH.size();
 
    pll vec_l = p2v(CH[0], CH[n - 1]);
    pll vec_r = p2v(CH[0], CH[1]);
 
    pll vec_c = p2v(CH[0], point);
 
    if (ccw(vec_l, vec_c) > 0) return false;
    if (ccw(vec_r, vec_c) < 0) return false;
 
    int l = 1, r = n - 1;
    while (l + 1 < r) // 이분탐색으로 점이 있는 구간을 찾는다
    {
        int m = (l + r) / 2;
 
        pll vec_m = p2v(CH[0], CH[m]);
        if (ccw(vec_m, vec_c) > 0) l = m;
        else r = m;
    }
 
    pll v1 = p2v(CH[l], point);
    pll v2 = p2v(point, CH[l + 1]);
 
    return ccw(v1, v2) < 0;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < n; i++)
    {
        ll x, y; cin >> x >> y;
        CH[0].push_back({ x,y });
    }
    for (int i = 0; i < m; i++)
    {
        ll x, y; cin >> x >> y;
        CH[1].push_back({ x,y });
    }
 
    int cnt = 0;
    for (int i = 0; i < k; i++)
    {
        ll x, y; cin >> x >> y;
        if (!isInside(CH[0], { x,y }) || isInside(CH[1], { x,y })) cnt++;
    }
 
    if (!cnt) cout << "YES";
    else cout << cnt;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217