point in convex polygon, 볼록 다각형 내부 점, convex polygon point containment, binary search on angle
정의
볼록 다각형 내부 점 판정 은 볼록 다각형(convex polygon) 과 하나의 점이 주어졌을 때, 점이 다각형의 내부/경계/외부 중 어디에 있는지 O(log N) 에 판별하는 알고리즘. N 은 꼭짓점 개수. 다각형이 반드시 볼록 (내각 180도 미만) 이어야 하며, 꼭짓점이 반시계(CCW) 또는 시계(CW) 순서로 주어져야 한다.
문제 상황과 동기
Q 개의 점이 볼록 N 각형 내부에 있는지 묻는 문제.
naive: 모든 변에 대해 CCW 검사를 일일이 수행. O(N Q). N=10^5, Q=10^5 면 불가능.
binary search on angle: O(N) 전처리 + O(log N) 쿼리. 총 O(N + Q log N).
핵심 통찰: 볼록 다각형의 꼭짓점은 한 점(p_0) 을 기준으로 각도순으로 정렬되어 있다. 임의의 점 q 에 대해, q 가 속하는 “쐐기” (p_0, p_i, p_{i+1}) 를 이분 탐색으로 찾고, 그 삼각형 내부에 q 가 있는지 CCW 한 번으로 확인.
시각화
핵심 아이디어
invariant: 볼록 다각형의 꼭짓점 p_0 에서 다른 꼭짓점으로의 방향 벡터는 각도 순서 로 정렬되어 있다.
1. p_1 ... p_{N-1} 이 p_0 를 기준으로 반시계 방향 정렬2. 쿼리 점 q 에 대해, p_0 에서 q 로의 벡터가 어느 구간 (p_0, p_i) 와 (p_0, p_{i+1}) 사이에 있는지 이분 탐색3. q 가 삼각형 (p_0, p_i, p_{i+1}) 내부에 있는지 CCW 로 확인
방향 판정
결과
CCW(p_0, p_i, q) > 0
q 가 왼쪽: i 를 오른쪽으로
CCW(p_0, p_i, q) ≤ 0
q 가 오른쪽: i 를 왼쪽으로
CCW(p_i, p_{i+1}, q) ≥ 0
q 가 내부 또는 경계
그 외
외부
알고리즘
INPUT: convex polygon P[0..N-1] (CCW order), query point qOUTPUT: IN / OUT / ON// 1. q 가 P[0] 과 같은 점인지 확인if P[0] == q: return ON// 2. q 가 P[0]->P[1] 과 P[0]->P[N-1] 사이에 있는지 확인if CCW(P[0], P[1], q) < 0 or CCW(P[0], P[N-1], q) > 0: return OUT// 3. 이분 탐색: q 가 속하는 wedge 찾기lo = 1, hi = N - 1while hi - lo > 1: mid = (lo + hi) / 2 if CCW(P[0], P[mid], q) >= 0: lo = mid else: hi = mid// 4. lo 와 lo+1 로 이루어진 삼각형 내부 확인if CCW(P[lo], P[lo+1], q) >= 0: if q 가 P[lo] 또는 P[lo+1] 경계 위: return ON return INreturn OUT
구현
// 볼록 다각형 내부 점 판정 O(log N)#include <bits/stdc++.h>using namespace std;using ll = long long;struct Point { ll x, y; };int ccw(Point a, Point b, Point c) { ll ret = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); if (ret > 0) return 1; if (ret < 0) return -1; return 0;}string pointInConvexPolygon(vector<Point>& P, Point q) { int n = P.size(); if (ccw(P[0], P[1], q) < 0 || ccw(P[0], P[n-1], q) > 0) return "OUT"; if (ccw(P[0], P[1], q) == 0) { if (q.x >= min(P[0].x, P[1].x) && q.x <= max(P[0].x, P[1].x) && q.y >= min(P[0].y, P[1].y) && q.y <= max(P[0].y, P[1].y)) return "ON"; return "OUT"; } int lo = 1, hi = n - 1; while (hi - lo > 1) { int mid = (lo + hi) / 2; if (ccw(P[0], P[mid], q) >= 0) lo = mid; else hi = mid; } int c = ccw(P[lo], P[lo+1], q); if (c > 0) return "IN"; if (c < 0) return "OUT"; return "ON";}int main() { int n, q; cin >> n >> q; vector<Point> P(n); for (auto& p : P) cin >> p.x >> p.y; while (q--) { Point qp; cin >> qp.x >> qp.y; cout << pointInConvexPolygon(P, qp) << "\n"; }}
# 볼록 다각형 내부 점 판정 (binary search on angle)import sysinput = sys.stdin.readlinedef ccw(ax, ay, bx, by, cx, cy): return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)def inside(P, qx, qy): n = len(P) if ccw(P[0][0], P[0][1], P[1][0], P[1][1], qx, qy) < 0: return "OUT" if ccw(P[0][0], P[0][1], P[-1][0], P[-1][1], qx, qy) > 0: return "OUT" lo, hi = 1, n - 1 while hi - lo > 1: mid = (lo + hi) // 2 if ccw(P[0][0], P[0][1], P[mid][0], P[mid][1], qx, qy) >= 0: lo = mid else: hi = mid c = ccw(P[lo][0], P[lo][1], P[lo+1][0], P[lo+1][1], qx, qy) if c > 0: return "IN" if c < 0: return "OUT" return "ON"n, q = map(int, input().split())P = [tuple(map(int, input().split())) for _ in range(n)]for _ in range(q): x, y = map(int, input().split()) print(inside(P, x, y))
// 볼록 다각형 내부 점 판정 O(log N)import java.util.*;import java.io.*;public class Main { static long ccw(long ax, long ay, long bx, long by, long cx, long cy) { return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax); } static String inside(long[][] P, long qx, long qy) { int n = P.length; if (ccw(P[0][0], P[0][1], P[1][0], P[1][1], qx, qy) < 0 || ccw(P[0][0], P[0][1], P[n-1][0], P[n-1][1], qx, qy) > 0) return "OUT"; int lo = 1, hi = n - 1; while (hi - lo > 1) { int mid = (lo + hi) / 2; if (ccw(P[0][0], P[0][1], P[mid][0], P[mid][1], qx, qy) >= 0) lo = mid; else hi = mid; } long c = ccw(P[lo][0], P[lo][1], P[lo+1][0], P[lo+1][1], qx, qy); if (c > 0) return "IN"; if (c < 0) return "OUT"; return "ON"; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[][] P = new long[n][2]; for (int i = 0; i < n; i++) { st = new StringTokenizer(br.readLine()); P[i][0] = Long.parseLong(st.nextToken()); P[i][1] = Long.parseLong(st.nextToken()); } StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(br.readLine()); long qx = Long.parseLong(st.nextToken()); long qy = Long.parseLong(st.nextToken()); sb.append(inside(P, qx, qy)).append('\n'); } System.out.print(sb); }}
💬 댓글