교차하는 볼록 다각형이 여러 개 있습니다. 나는 많은 이들이 교차하는 지역을 찾고 싶다. 이미지에서 "피크"라고 생각할 수 있습니다. 나는 지역 봉우리를 찾고있다.다중 볼록 다각형 교차점
두 개의 다각형을 교차시키는 소프트웨어가 있습니다. 이제 모든 가능한 교차점을 계산하지 않고 최고점을 계산하는 방법에 대해 생각하고 있습니다 (지수 시간!).
누군가가 힌트를 가지고 있습니까?
주어진 k 개의 볼록 다각형. 모든 다각형의 경계가 n 개의 선분으로 주어진다고 가정합니다. 각 선분은 속한 다각형과 내부면에 대한 참조를 가지고 있습니다. 선분의 정점을 x 좌표로 정렬합시다. 이제 왼쪽에서 오른쪽으로 라인 스윕을 시작합니다.
대부분의 O (k) 번 스윕 중에 모든 다각형이 볼록하므로 다각형이 시작되고 끝납니다. 시작 이벤트에서 스윕 라인 상태를 살펴보고 다른 폴리곤이 얼마나 많은 수를 차지하고 있는지 확인합니다. 어느 O (n) 시간이 걸립니다.
n 개 세그먼트의 경우 라인 스윕은 O (n log n + k^2 + kn) 시간을 얻는 시작 이벤트 처리를 추가하는 O (n log n + k^2) 시간의 모든 교차점을 제공합니다. 선분의 참조를 사용하여 모든 영역 (선분)에 현재 덮고있는 폴리곤 수를 할당 할 수 있어야합니다.
빠른 답변 감사합니다. – yar
맞다면 다음 예제는 작동하지 않습니다. 두 개의 마름모꼴 모양의 다각형이 가운데에서 교차하지만 왼쪽과 오른쪽 부분이 교차하지 않습니다. 스윕 라인은 왼쪽에서 오른쪽으로 진행되므로 폴리곤이 시작될 때마다 1 개의 다각형이 계산되고 마지막에는 0 개의 다각형이 계산됩니다. 우리가 교차로를 놓친이 방법, 맞죠? – yar
@yar sweepline 접근 방식의 가장 큰 장점은 이러한 교차점을 찾는 것입니다. 우리는 이미 교차점 앞에 중첩 된 폴리곤의 수를 알기 때문에 교차점의 유형에 따라 각 세그먼트에 할당 된 숫자 만 늘리거나 줄여야합니다. 우리가 세그먼트의 상대적인 내부가 어디에 있는지 알기 때문에 우리는 국지적으로 무엇을해야 하는지를 결정할 수 있습니다. – gue