math - 半径rのn個の円の交点の面積

Question

Prob Statement: 'N' 個の等しい半径の円が (-) 無限大から (+) 無限大までグラフにプロットされます。交差の総面積、つまり 2 つ以上の円で覆われるグラフ上のすべての面積を求めてください。

Answer 1

最初に訂正: これらは円ではありません。それらは楕円です (円は a = b の楕円の特殊なケースです)。2 つの楕円の交点を計算できるため、N 個の楕円が与えられた場合、各ペアをチェックする必要があるため、全体の操作は O(n ² ) (交点操作が何であれ乗算されます) です。

楕円の交点 と 交差する楕円の領域 を見てください。

編集:円の交点はより簡単な問題ですが、同じ原則に従います。Intersection Of Two CirclesとCircle-Circle Intersectionを見てください。

Answer 2

最も簡単な (必ずしも最速または「最良」であるとは限りません) コーディング方法は、すべての円を含む境界ボックスを見つけてから、数値確率法を使用して統合することです。

賢くなれば、おそらく円をグループ化し、それらを個別にボックス化できます。つまり、多数のバウンディング ボックスで作業できます。また、特定の特殊なケースも正確に処理します。

しかし、純粋な確率論的手法には、実装が簡単であるという利点があります (ただし、処理が遅くなる可能性があります)。

これは、「おおよその」(ただし任意に正しいに近い) 回答が得られる場合にのみ受け入れられます。