도형 불 연산 (Geometric Boolean Operations) 은 두 다각형(또는 임의의 폐곡선)에 대해 합집합(union), 교집합(intersection), 차집합(difference)을 계산하는 기하 알고리즘. 대표적으로 Sutherland-Hodgman (convex clipping) 과 Weiler-Atherton (general polygon clipping) 이 알려져 있음.
문제 상황과 동기
두 다각형 A, B 가 주어졌을 때 A ∪ B, A ∩ B, A - B (또는 B - A) 를 구해야 함.
Naive 접근: 각 변을 무한 직선으로 확장 후 교차점을 찾고 폐곡선을 재구성. O(NM) 이지만 self-intersection / 구멍 처리 까다로움.
핵심 통찰: 한 다각형의 각 변을 clipping edge 로 삼아 반대 다각형을 잘라내면 출력 폴리곤이 자연스럽게 생성. Weiler-Atherton 은 교차점 리스트를 따라가며 출력 링을 구성.
PS 위치: convex polygon clipping 은 Sutherland-Hodgman 으로 O(N+M). 일반 polygon 은 Weiler-Atherton 필요.
시각화
핵심 아이디어
Sutherland-Hodgman: convex clipping window 의 각 edge 에 대해, subject polygon 의 점들을 inside/outside 판정. 출력 리스트를 누적.
for each clip edge (from clip polygon): for each edge (S->E) of subject: if S inside, E inside -> output E if S inside, E outside -> output intersection if S outside, E inside -> output intersection, then E if S outside, E outside -> output nothing
Weiler-Atherton: 교차점을 표시한 후, entering/leaving 에 따라 출력 링크를 순회.
알고리즘
Sutherland-Hodgman(subject, clip): output = subject for each edge of clip: input = output; output = [] for each edge S->E in input: if inside(E, clipEdge): if not inside(S, clipEdge): output.push(intersect(S,E, clipEdge)) output.push(E) else if inside(S, clipEdge): output.push(intersect(S,E, clipEdge)) return output
구현
// Sutherland-Hodgman convex polygon clipping#include <bits/stdc++.h>using namespace std;using ld = long double;struct Pt { ld x, y; };ld cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }Pt sub(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }Pt add(Pt a, Pt b) { return {a.x+b.x, a.y+b.y}; }Pt mul(Pt a, ld t) { return {a.x*t, a.y*t}; }ld dot(Pt a, Pt b) { return a.x*b.x + a.y*b.y; }bool inside(Pt p, Pt a, Pt b) { return cross(sub(b,a), sub(p,a)) >= 0; // clockwise}Pt intersect(Pt p1, Pt p2, Pt a, Pt b) { Pt v1 = sub(p2,p1), v2 = sub(b,a), v3 = sub(a,p1); ld t = cross(v2,v3) / cross(v1,v2); return add(p1, mul(v1, t));}vector<Pt> clip(vector<Pt> subj, vector<Pt> clip) { vector<Pt> out = subj; int m = clip.size(); for (int i = 0; i < m; i++) { Pt a = clip[i], b = clip[(i+1)%m]; vector<Pt> in = out; out.clear(); int n = in.size(); for (int j = 0; j < n; j++) { Pt cur = in[j], prv = in[(j+n-1)%n]; bool curIn = inside(cur, a, b); bool prvIn = inside(prv, a, b); if (curIn) { if (!prvIn) out.push_back(intersect(prv, cur, a, b)); out.push_back(cur); } else if (prvIn) { out.push_back(intersect(prv, cur, a, b)); } } } return out;}int main() { int n; cin >> n; vector<Pt> subj(n); for (auto& p : subj) cin >> p.x >> p.y; int m; cin >> m; vector<Pt> clipPoly(m); for (auto& p : clipPoly) cin >> p.x >> p.y; auto res = clip(subj, clipPoly); cout << res.size() << "\n"; for (auto& p : res) cout << p.x << " " << p.y << "\n";}
# Sutherland-Hodgman convex polygon clippingdef cross(a, b): return a[0]*b[1] - a[1]*b[0]def sub(a, b): return (a[0]-b[0], a[1]-b[1])def add(a, b): return (a[0]+b[0], a[1]+b[1])def mul(a, t): return (a[0]*t, a[1]*t)def inside(p, a, b): return cross(sub(b,a), sub(p,a)) >= 0def intersect(p1, p2, a, b): v1 = sub(p2,p1); v2 = sub(b,a); v3 = sub(a,p1) t = cross(v2,v3) / cross(v1,v2) return add(p1, mul(v1, t))def clip(subj, clip_poly): out = subj[:] m = len(clip_poly) for i in range(m): a, b = clip_poly[i], clip_poly[(i+1)%m] inp = out; out = [] n = len(inp) for j in range(n): cur, prv = inp[j], inp[(j+n-1)%n] cur_in, prv_in = inside(cur,a,b), inside(prv,a,b) if cur_in: if not prv_in: out.append(intersect(prv,cur,a,b)) out.append(cur) elif prv_in: out.append(intersect(prv,cur,a,b)) return outn = int(input())subj = [tuple(map(float, input().split())) for _ in range(n)]m = int(input())clip_poly = [tuple(map(float, input().split())) for _ in range(m)]res = clip(subj, clip_poly)print(len(res))for p in res: print(f"{p[0]} {p[1]}")
import java.util.*;import java.io.*;public class Main { static class Pt { double x,y; Pt(double x,double y){this.x=x;this.y=y;} } static double cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; } static Pt sub(Pt a, Pt b) { return new Pt(a.x-b.x, a.y-b.y); } static Pt add(Pt a, Pt b) { return new Pt(a.x+b.x, a.y+b.y); } static Pt mul(Pt a, double t) { return new Pt(a.x*t, a.y*t); } static boolean inside(Pt p, Pt a, Pt b) { return cross(sub(b,a), sub(p,a)) >= 0; } static Pt intersect(Pt p1, Pt p2, Pt a, Pt b) { Pt v1=sub(p2,p1), v2=sub(b,a), v3=sub(a,p1); double t = cross(v2,v3) / cross(v1,v2); return add(p1, mul(v1, t)); } static List<Pt> clip(List<Pt> subj, List<Pt> clip) { List<Pt> out = new ArrayList<>(subj); for (int i=0; i<clip.size(); i++) { Pt a=clip.get(i), b=clip.get((i+1)%clip.size()); List<Pt> in = out; out = new ArrayList<>(); for (int j=0; j<in.size(); j++) { Pt cur=in.get(j), prv=in.get((j+in.size()-1)%in.size()); boolean curIn=inside(cur,a,b), prvIn=inside(prv,a,b); if (curIn) { if (!prvIn) out.add(intersect(prv,cur,a,b)); out.add(cur); } else if (prvIn) out.add(intersect(prv,cur,a,b)); } } return out; } public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); int n=Integer.parseInt(br.readLine()); List<Pt> subj=new ArrayList<>(); for (int i=0; i<n; i++) { StringTokenizer st=new StringTokenizer(br.readLine()); subj.add(new Pt(Double.parseDouble(st.nextToken()),Double.parseDouble(st.nextToken()))); } int m=Integer.parseInt(br.readLine()); List<Pt> clipP=new ArrayList<>(); for (int i=0; i<m; i++) { StringTokenizer st=new StringTokenizer(br.readLine()); clipP.add(new Pt(Double.parseDouble(st.nextToken()),Double.parseDouble(st.nextToken()))); } List<Pt> res=clip(subj, clipP); System.out.println(res.size()); for (Pt p:res) System.out.println(p.x+" "+p.y); }}
stdin
40 010 010 100 1045 515 515 155 15
결과
45 510 510 105 10
복잡도
항목
값
Sutherland-Hodgman
O(N * M) (각 clip edge 마다 전체 순회)
Weiler-Atherton
O(N + M + K) (K = 교차점 개수)
공간
O(N + M)
N, M 은 각각 subject, clip polygon 의 꼭짓점 개수.
변형 / 활용
Union (합집합): A, B 의 outside 부분을 취합.
Intersection (교집합): Sutherland-Hodgman 직접 적용.
Difference (차집합): A - B 는 B 의 반대 방향 edge 로 clipping.
💬 댓글