반경 'r'인 n 개의 원이 교차하는 영역

Question

Prob 명세서 : '-'무한대부터 (+) 무한대까지 'N'같은 반경 원이 그래프로 그려집니다. 전체 교차 영역을 찾으십시오. 두 개 이상의 원으로 덮여있는 그래프상의 영역.

Answer 1

먼저 수정 사항입니다. 이것은 원이 아닙니다. 그것들은 타원입니다 (원은 타원의 특별한 경우이고 a = b 인 경우입니다). 두 개의 타원의 교점을 계산할 수 있으므로 각 쌍을 검사해야하는 N 개의 타원이 있으므로 전체 연산은 O (n) (교차 연산이 무엇이든간에 곱함)입니다.

Intersection of Ellipses 및 The Area of Intersecting Ellipses을 살펴보십시오.

편집 : 원의 교차점은 쉬운 문제이지만 동일한 원칙을 따릅니다. Intersection Of Two Circles 및 Circle-Circle Intersection을 살펴보십시오.

Answer 2

코드를 작성하는 가장 쉬운 방법 (가장 빠르고 가장 좋은 것은 아닙니다)은 모든 원을 포함하는 경계 상자를 찾은 다음 수치 적 확률 적 방법을 사용하여 통합하는 것입니다.

이제 똑똑해지면서 원을 그룹화하고 개별적으로 상자에 넣을 수 있습니다. 즉 여러 경계 상자에서 작업 할 수 있습니다. 심지어 특정 특수 사례를 정확하게 처리합니다.

그러나 순수 확률 론적 방법은 구현하기가 쉽지만 (잠재적으로 느린) 아름다움이 있습니다.

"근사"(그러나 임의로 정확한 답변에 가까운) 답변을 기꺼이 사용하려는 경우에만 허용됩니다.