여러 다각형을 교차하는 방법은 무엇입니까?

Question

다음 입력 및 출력을 가진 알고리즘을 찾고 있습니다.

입력 : 평면의 다각형 집합입니다.예 :P1 ... Pn 및 S. (P1 ... Pn은 오목하고 S는 볼록합니다.)

출력 : S의 차이와 P1 ... Pn의 합집합과 같은이 평면의 다각형 집합 영역

두 개의 다각형을 교차하거나 병합하는 알고리즘을 찾았습니다.하지만 각각의 작업이 여러 다각형을 생성 할 수 있기 때문에 순진하게 수행하면 수많은 다각형을 만들었습니다.

그래서 : 여러 다각형의 교차점을 어떻게 처리할까요?

내가 추구하는 영역 만 영역이므로 모든 다각형이 함께 연결 되어도 괜찮을 것입니다.내 생각은 방향성 다각형을 사용하여 구멍을 시뮬레이션하는 것이었지만 n이 폭발 할 수있는 "최소 표현"이 있는지 다시 확인하는 데 문제가 있습니다.[내가 무슨 말을하는지 이해합니까?꽤 이상 해요 ...)

Answer 1

모든 가장자리를 함께 스윕 라인 알고리즘 으로 만들 수 있습니다.최적이 아닐 수도 있지만 (?) 최소한 원하는 최소한의 표현을 얻을 수 있습니다.

Answer 2

한 가지 해결책은 각 다각형을 여러 개의 삼각형으로 변환하는 것입니다.이렇게하면 삼각형에서 사소하게 동일한 기능을 수행 할 수 있기 때문에 영역 집합 간의 합집합 / 교차 / 차이를 찾기가 매우 쉽습니다 (두 삼각형에 대한 결과는 최대 6 개의 삼각형을 포함 할 수 있음).

Answer 3

가장 간단한 방법은 오목한 다각형을 볼록한 다각형으로 분해하는 것입니다.그러면 두 개의 볼록한 다각형이 교차하는 것은 거의 사소한 일입니다.