的正好3個圈

Question

重疊的區域數目我有任務在那裏我有任何數量的圈子。我所知道的一個是它的中心和半徑。現在我需要找到正好是 3圈的重疊區域的數量。我試圖解決它知道當他們的中心之間的距離短於半徑的總和時圓圈重疊，但它讓我無處可去。

Answer 1

一個掃線算法應該做的工作。

閱讀有關一般here掃線算法，對一個特定的（非常重要）算法here。這個問題的算法的總體結構將類似於Bentley-Ottmann算法的結構。下面是一些細節（不是完整的描述，而是一個草圖;完整的描述

在每個圓上的所有最左邊（最小X）和最右邊（最大X）點，所有這些點的X座標。他們

一個優先級隊列。運行沿X軸的垂直掃描線，線中包含的Y座標的集合點的在那裏它與在當前X座標圈，由Y.

排序相交一旦掃描線打最左邊的圓圈點，將其添加到收藏兩次 - 一次是針對上半圓，一次用於下半圓一旦掃描線擊中最右邊的圓點，刪除相應的集合點。跟蹤兩個連續點之間的每個間隔由圓圈覆蓋的次數。跟蹤這些區域的身份。每當屬於不同圓圈的兩個點彼此相鄰時，計算它們的交點，並將它們插入點隊列。每當掃描線遇到交點時，交換收集中的相應點並調整區域標識和重疊計數。

這很容易通過繪製某些圈子裏的一張紙，不同的着色各個區域，並緩慢移動在繪圖尺，指出它是如何與社交圈和區域相交以可視化的算法。

亦谷「行掃描算法」， 「圓」。