[algorithm] 겹치는 원의 결합 영역
나는 최근에 4 개의 원 (중간 점과 반지름)이 있고이 원들의 결합 면적을 계산해야하는 문제를 발견했습니다.
예시 이미지 :
두 개의 원의 경우 매우 쉽습니다.
삼각형 안에 있지 않은 각 원 영역의 비율을 계산 한 다음 삼각형의 영역을 계산할 수 있습니다.
그러나 두 개 이상의 원이있을 때 사용할 수있는 영리한 알고리즘이 있습니까?
답변
바깥 둘레의 모든 원 교차점을 찾으십시오 (예 : 다음 다이어그램의 B, D, F, H). 해당 원의 중심과 함께 연결하여 다각형을 형성하십시오. 원의 결합 영역은 다각형 영역 + 연속 교차점과 그 사이의 원 중심으로 정의 된 원 슬라이스 영역입니다. 또한 모든 구멍을 고려해야합니다.
답변
나는 영리한 알고리즘이 있다고 확신하지만, 그것을 찾아야하는 것을 저장하는 멍청한 알고리즘이있다.
- 원 주위에 경계 상자를 두십시오.
- 경계 상자 내에서 임의의 점을 생성합니다.
- 임의의 점이 원 중 하나 안에 있는지 알아 내십시오.
- 간단한 덧셈과 나눗셈으로 면적을 계산합니다 (proportion_of_points_inside * area_of_bounding_box).
물론 멍청하지만 :
- 원하는만큼 정확한 답을 얻을 수 있으며 더 많은 점수를 생성 할 수 있습니다.
- 내부 / 외부 구분을 계산할 수있는 모든 모양에 대해 작동합니다.
- 모든 코어를 사용할 수 있도록 아름답게 병렬화됩니다.
답변
Ants Aasma의 답변은 기본 아이디어를 제공했지만 좀 더 구체적으로 만들고 싶었습니다. 아래에있는 5 개의 원과 분해 된 방식을 살펴보세요.
- 파란색 점은 원 중심입니다.
- 빨간색 점은 원 경계 교차점입니다.
- 내부 가 흰색 인 빨간색 점 은 다른 원에 포함되지 않은 원 경계 교차점입니다 .
이 세 가지 유형의 점을 식별하는 것은 쉽습니다. 이제 노드가 파란색 점이고 내부가 흰색 인 빨간색 점인 그래프 데이터 구조를 구성하십시오. 모든 원에 대해 경계의 원 가운데 (파란색 점)와 교차점 (내부 흰색이 흰색 인 빨간색 점) 사이에 가장자리를 배치합니다.
이렇게하면 원 결합이 쌍으로 분리되고 원래 결합 (즉, 파티션)을 덮는 다각형 (파란색 음영)과 원형 원형 조각 (녹색 음영) 집합으로 분해됩니다. 여기의 각 조각은 면적을 계산하기 쉬운 것이기 때문에 조각의 면적을 합산하여 합집합 면적을 계산할 수 있습니다.
답변
이전 솔루션과 다른 솔루션의 경우 쿼드 트리를 사용하여 임의 정밀도로 추정을 생성 할 수 있습니다.
사각형이 내부 또는 외부에 있는지 또는 모양과 교차하는지 알 수있는 경우 모든 모양 결합에도 적용됩니다.
각 셀에는 비어 있음, 전체, 부분 상태 중 하나가 있습니다.
알고리즘은 낮은 해상도 (예를 들어 비어있는 것으로 표시된 4 개의 셀)로 시작하는 쿼드 트리의 원을 “그리는”것으로 구성됩니다. 각 셀은 다음 중 하나입니다.
- 하나 이상의 원 안에있는 셀을 가득 찬 것으로 표시하고
- 모든 원 밖에서 셀을 비워두고
- 그렇지 않으면 셀을 부분적으로 표시하십시오.
완료되면 면적 추정치를 계산할 수 있습니다. 전체 셀은 하한, 빈 셀은 상한, 부분 셀은 최대 면적 오류를 제공합니다.
오류가 너무 크면 정확한 정밀도를 얻을 때까지 부분 셀을 다듬습니다.
많은 특수한 경우를 처리해야하는 기하학적 방법보다 구현하기가 더 쉬울 것이라고 생각합니다.
답변
나는 두 개의 교차하는 원의 경우에 대한 접근 방식을 좋아합니다. 여기 더 복잡한 예제에 대해 동일한 접근 방식의 약간의 변형을 사용하는 방법이 있습니다.
더 많은 수의 반 겹치는 원에 대한 알고리즘을 일반화하는 데 더 나은 통찰력을 줄 수 있습니다.
여기서 차이점은 중심을 연결하는 것으로 시작한다는 것입니다 (원이 교차하는 곳이 아닌 원의 중심 사이에 정점이 있음). 이것이 더 잘 일반화되도록 해준다고 생각합니다.
(실제로 monte-carlo 방법이 가치가있을 수 있습니다)
(출처 : secretGeek.net )
답변
연속적인 답이 아닌 불연속적인 답을 원한다면 픽셀 페인팅 알고리즘과 비슷한 것을 할 수 있습니다.
그리드에 원을 그린 다음 대부분이 원 안에 포함 된 경우 그리드의 각 셀에 색상을 지정합니다 (즉, 영역의 50 % 이상이 원 중 하나 안에 있음). 전체 그리드 (그리드가 원으로 덮인 모든 영역에 걸쳐 있음)에 대해이 작업을 수행 한 다음 그리드에서 색상이 지정된 셀 수를 계산합니다.
답변
흠, 매우 흥미로운 문제입니다. 내 접근 방식은 아마도 다음과 같은 것입니다.
- 임의의 수의 원 사이의 교차 영역이 무엇인지 알아내는 방법을 찾으세요. 즉, 3 개의 원이 있다면 그 원 사이의 교차점이 무엇인지 알아낼 수 있어야합니다. “Monte-Carlo”방법은이를 근사화하는 좋은 방법입니다 ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
- 다른 더 큰 원에 완전히 포함 된 모든 원을 제거합니다 (두 원의 중심 사이의 반경과 거리 계수를보십시오). 필수라고 생각하지 않습니다.
- 2 개의 원을 선택하고 (A와 B라고 부름) 다음 공식을 사용하여 총 면적을 계산합니다.
(이것은 원형이든 아니든 모든 모양에 해당됩니다)
area(A∪B) = area(A) + area(B) - area(A∩B)
Where A ∪ B는 A 유니온 B를 A ∩ B의미하고 A는 B와 교차 함을 의미합니다 (첫 번째 단계에서이 문제를 해결할 수 있습니다.
- 이제 계속해서 원을 추가하고 원의 영역과 원 사이의 교차 영역의 합계 / 빼기로 추가 된 영역을 계속 계산합니다. 예를 들어 3 개의 원 (추가 원 C라고 부름)의 경우 다음 공식을 사용하여 면적을 계산합니다.
(위에서 A로 대체 된 것과 동일 A∪B)
area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)
어디 area(A∪B)우리는 그냥 일을하고 area((A∪B)∩C)찾을 수 있습니다 :
area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)
위에서 다시 지역 (A∩B∩C)을 찾을 수 있습니다.
까다로운 부분은 마지막 단계입니다. 더 많은 원이 추가 될수록 더 복잡해집니다. 유한 합집합을 사용하여 교차 영역을 작업하는 데 확장이 있다고 믿습니다. 그렇지 않으면 재귀 적으로 작업 할 수 있습니다.
또한 Monte-Carlo를 사용하여 반복 영역을 근사화하는 것과 관련하여 임의의 수의 원의 교차점을 정확히 계산할 수있는 4 개의 원의 교차점으로 줄일 수 있다고 생각합니다 (이 작업을 수행하는 방법을 모릅니다 하나).
이 작업을 수행하는 더 좋은 방법이있을 것입니다. 추가 된 각 추가 원에 대해 복잡성이 상당히 증가합니다 (아마도 기하 급수적으로 증가하지만 확실하지 않습니다).
