point in polygon, ray casting, 다각형 내부 점 판정, crossing number, even-odd rule
정의
다각형 내부 점 판정 (Point in Polygon, PIP) 은 단순 다각형 (볼록 또는 오목) 과 하나의 점이 주어졌을 때, 점이 내부/경계/외부 중 어디에 있는지 판별하는 문제. Ray casting (ray crossing) 알고리즘이 가장 일반적으로 사용되며, O(N) 시간에 동작한다. N 은 꼭짓점 개수.
문제 상황과 동기
단순 다각형 (볼록/오목 구분 없음) 과 하나의 점. 오목 다각형에서는 CCW 만으로 일관된 판정이 불가능.
Naive: 각 변마다 점과의 위치 관계를 확인하는 CCW 검사는 볼록일 때만 O(N). 오목에선 실패.
Ray casting: 점에서 임의의 방향으로 반직선을 그려 다각형 변과의 교차 횟수로 판정. O(N).
핵심 통찰: 다각형의 변은 내부와 외부를 가르는 경계선. 반직선이 변과 교차할 때마다 내부/외부 패리티가 바뀐다. 최종 교차 횟수가 홀수면 내부, 짝수면 외부.
시각화
핵심 아이디어
even-odd rule (홀짝 법칙): 점 p 에서 오른쪽으로 수평 반직선을 긋는다. 이 반직선과 다각형의 변이 교차하는 횟수를 센다. 교차 횟수 % 2 == 1 → IN 교차 횟수 % 2 == 0 → OUT
조건
판정
교차 횟수 = 홀수
내부 (IN)
교차 횟수 = 짝수 (0 포함)
외부 (OUT)
점이 변 위에 있음
경계 (ON)
반직선 방향은 어디든 상관없으나, 오른쪽 수평 이 구현이 가장 간단.
알고리즘
INPUT: polygon P[0..N-1] (CCW or CW), query point qOUTPUT: IN / ON / OUTcount = 0for i = 0..N-1: j = (i + 1) % N if q is on segment(P[i], P[j]): return ON // P[i].y < q.y <= P[j].y (upward crossing) // 또는 P[j].y < q.y <= P[i].y (downward crossing) if (P[i].y <= q.y < P[j].y) or (P[j].y <= q.y < P[i].y): // 반직선과 변의 교차 x 좌표 계산 x_intersect = P[i].x + (q.y - P[i].y) * (P[j].x - P[i].x) / (P[j].y - P[i].y) if q.x < x_intersect: count++return count % 2 == 1 ? IN : OUT
주의: 한쪽 끝점만 inclusive 로 처리하여 꼭짓점 중복 교차 방지.
구현
// Ray casting O(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;}bool onSegment(Point a, Point b, Point q) { if (ccw(a, b, q) != 0) return false; return min(a.x, b.x) <= q.x && q.x <= max(a.x, b.x) && min(a.y, b.y) <= q.y && q.y <= max(a.y, b.y);}string pip(vector<Point>& P, Point q) { int n = P.size(), cnt = 0; for (int i = 0; i < n; i++) { int j = (i + 1) % n; if (onSegment(P[i], P[j], q)) return "ON"; if ((P[i].y <= q.y && q.y < P[j].y) || (P[j].y <= q.y && q.y < P[i].y)) { double x_intersect = P[i].x + (double)(q.y - P[i].y) * (P[j].x - P[i].x) / (P[j].y - P[i].y); if (q.x < x_intersect) cnt++; } } return cnt % 2 ? "IN" : "OUT";}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 << pip(P, qp) << "\n"; }}
# Ray casting O(N) point in polygonimport sysinput = sys.stdin.readlinedef ccw(ax, ay, bx, by, cx, cy): return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)def on_seg(x1, y1, x2, y2, qx, qy): if ccw(x1, y1, x2, y2, qx, qy) != 0: return False return min(x1, x2) <= qx <= max(x1, x2) and min(y1, y2) <= qy <= max(y1, y2)def pip(P, qx, qy): n, cnt = len(P), 0 for i in range(n): x1, y1 = P[i] x2, y2 = P[(i + 1) % n] if on_seg(x1, y1, x2, y2, qx, qy): return "ON" if (y1 <= qy < y2) or (y2 <= qy < y1): x_int = x1 + (qy - y1) * (x2 - x1) / (y2 - y1) if qx < x_int: cnt += 1 return "IN" if cnt % 2 else "OUT"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(pip(P, x, y))
// Ray casting O(N) point in polygonimport 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 boolean onSeg(long x1, long y1, long x2, long y2, long qx, long qy) { if (ccw(x1, y1, x2, y2, qx, qy) != 0) return false; return Math.min(x1, x2) <= qx && qx <= Math.max(x1, x2) && Math.min(y1, y2) <= qy && qy <= Math.max(y1, y2); } static String pip(long[][] P, long qx, long qy) { int n = P.length, cnt = 0; for (int i = 0; i < n; i++) { long x1 = P[i][0], y1 = P[i][1]; long x2 = P[(i+1)%n][0], y2 = P[(i+1)%n][1]; if (onSeg(x1, y1, x2, y2, qx, qy)) return "ON"; if ((y1 <= qy && qy < y2) || (y2 <= qy && qy < y1)) { double xInt = x1 + (double)(qy - y1) * (x2 - x1) / (y2 - y1); if (qx < xInt) cnt++; } } return cnt % 2 == 1 ? "IN" : "OUT"; } 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(pip(P, qx, qy)).append('\n'); } System.out.print(sb); }}
💬 댓글