113

最近、4 つの円 (中点と半径) があり、これらの円の和集合の面積を計算する必要があるという問題に遭遇しました。

画像例:

2 つの円の場合は非常に簡単です。

三角形内にない各円の面積の割合を計算してから、三角形の面積を計算できます。

しかし、2 つ以上の円がある場合に使用できる巧妙なアルゴリズムはありますか?

4

15 に答える 15

100

外周上のすべての円の交点を見つけます (たとえば、次の図の B、D、F、H)。それらを対応する円の中心と一緒に接続して、多角形を形成します。円の和集合の面積は、多角形の面積 + 連続する交差点とそれらの間の円の中心によって定義される円スライスの面積です。穴も考慮する必要があります。

サークルオーバーラップ

于 2009-11-03T14:47:10.403 に答える
32

確かに賢いアルゴリズムがあると思いますが、探す手間を省くためのばかげたアルゴリズムを次に示します。

  • 円の周りにバウンディング ボックスを置きます。
  • バウンディング ボックス内にランダム ポイントを生成します。
  • ランダムな点がいずれかの円の内側にあるかどうかを調べます。
  • 簡単な加算と除算によって面積を計算します (proportion_of_points_inside*area_of_bounding_box)。

確かにそれはばかげていますが、：

  • より多くのポイントを生成するだけで、必要なだけ正確な回答を得ることができます。
  • 内側と外側の区別を計算できる任意の形状で機能します。
  • 美しく並列化されるため、すべてのコアを使用できます。
于 2009-11-03T13:34:39.217 に答える
25

Ants Aasma の回答で基本的なアイデアが得られましたが、もう少し具体的にしたいと思いました。以下の 5 つの円と、それらがどのように分解されたかを見てください。

例

  • 青い点は円の中心です。
  • 赤い点は円の境界の交点です。
  • 内側が白い赤い点は、他のどの円にも含まれない円境界の交点です。

これら 3 種類のドットを識別するのは簡単です。ここで、ノードが青い点と白い内部の赤い点であるグラフ データ構造を作成します。すべての円について、境界上の円の中央 (青い点) とその交点 (内側が白い赤い点) の間にエッジを置きます。

これにより、円の和集合が一連の多角形 (青色の陰影) と円形のパイ片 (緑色の陰影) に分解されます。これらはペアごとにばらばらで、元の和集合 (つまり、パーティション) をカバーします。ここでの各ピースは面積を計算しやすいものなので、ピースの面積を合計することで和集合の面積を計算できます。

于 2014-06-04T16:06:16.147 に答える
17

前のソリューションとは異なるソリューションの場合、四分木を使用して任意の精度で推定を生成できます。

これは、正方形が形状の内側か外側か、または交差しているかどうかがわかれば、任意の形状結合にも機能します。

各セルには、空の状態、完全な状態、部分的な状態のいずれかがあります。

アルゴリズムは、低解像度 (たとえば、空としてマークされた 4 つのセル) から開始して、四分木の円を「描画」することで構成されます。各セルは次のいずれかです。

  • 少なくとも 1 つの円の内側にあるセルを満杯としてマークし、
  • すべての円の外側で、セルを空としてマークし、
  • それ以外の場合は、セルを部分としてマークします。

完了すると、面積の推定を計算できます。完全なセルは下限を示し、空のセルは上限を示し、部分的なセルは最大面積エラーを示します。

エラーが大きすぎる場合は、適切な精度が得られるまで部分セルを調整します。

これは、多くの特殊なケースを処理する必要がある可能性がある幾何学的方法よりも実装が簡単になると思います。

于 2009-11-03T15:37:14.657 に答える
13

2 つの交差する円の場合のアプローチが気に入っています。より複雑な例では、同じアプローチを少し変えて使用する方法を次に示します。

より多くの半重複円のアルゴリズムを一般化することについて、より良い洞察を与えるかもしれません。

ここでの違いは、中心をリンクすることから始めることです (したがって、円が交差する場所の間ではなく、円の中心の間に頂点があります)。これにより、より一般化できると思います。

（実際には、モンテカルロ法が価値があるかもしれません）

代替テキスト
(出典: secretGeek.net )

于 2009-11-03T14:05:42.627 に答える
4

(連続ではなく) 個別の回答が必要な場合は、ピクセル ペインティング アルゴリズムに似た処理を行うことができます。

グリッド上に円を描画し、グリッドの各セルが円内にほとんど含まれている場合 (つまり、その領域の少なくとも 50% がいずれかの円の内側にある場合) に色を付けます。グリッド全体 (グリッドが円で覆われたすべての領域にまたがる場所) に対してこれを行い、グリッド内の色付きのセルの数を数えます。

于 2009-11-03T16:20:41.260 に答える
3

私は、重なり合う星のフィールドをシミュレートする問題に取り組んでおり、大きな明るい星が暗い星を隠すことができる、密なフィールドの実際のディスク領域から真の星の数を推定しようとしています。私も厳密な形式的分析によってこれを実行できることを望んでいましたが、タスクのアルゴリズムを見つけることができませんでした。確率アルゴリズムによって直径が決定された緑色の円盤として青色の背景に星のフィールドを生成することで、それを解決しました。簡単なルーチンでそれらをペアにして、オーバーラップがあるかどうかを確認できます（スターペアを黄色に変えます）。次に、色のピクセルカウントにより、理論領域と比較するための観測領域が生成されます。これにより、真のカウントの確率曲線が生成されます。ブルートフォースかもしれませんが、問題なく機能しているようです。（出典：2from.com）

于 2009-12-02T00:09:17.230 に答える
3

うーん、非常に興味深い問題です。私のアプローチは、おそらく次のようなものになるでしょう。

  • 任意の数の円の間の交点の面積を計算する方法を考え出します。つまり、円が 3 つある場合、それらの円の交点を計算できるようにする必要があります。「モンテカルロ」法は、これを近似する良い方法です ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ )。
  • 別の大きな円に完全に含まれている円を削除します (半径と 2 つの円の中心間の距離のモジュラスを見てください)。必須ではないと思います。
  • 2 つの円 (A と B と呼びます) を選択し、次の式を使用して合計面積を計算します。

（これは、円であろうとなかろうと、どんな形にも当てはまります）

area(A∪B) = area(A) + area(B) - area(A∩B)

ここで、A がA ∪ BB の結合を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) を見つけることができます。

注意が必要なのは最後のステップです。円が追加されるほど、円は複雑になります。有限和集合との交点の面積を計算するための拡張があると思います。あるいは、再帰的に計算できるかもしれません。

また、モンテカルロを使用して交点の面積を概算することに関して、任意の数の円の交点をそれらの円の 4 つの交点に減らすことが可能であると信じています。これは正確に計算できます (これを行う方法がわかりません)。でも）。

おそらく、これを行うためのより良い方法があります-余分な円が追加されるたびに、複雑さが大幅に（おそらく指数関数的に、しかし私にはわかりません）増加します。

于 2009-11-03T14:42:03.583 に答える
2

これは、実際に実装するのが簡単で、任意に小さなエラーを生成するように調整できるアルゴリズムです。

  1. 同じ点を中心とする正多角形で各円を近似します
  2. 近似円の和集合である多角形を計算する
  3. マージされたポリゴンの面積を計算します

ステップ 2 と 3 は、計算幾何学から見つけやすい標準的なアルゴリズムを使用して実行できます。

明らかに、近似ポリゴンごとに使用する辺が多いほど、正確な答えに近づきます。内接ポリゴンと外接ポリゴンを使用して概算して、正確な答えの境界を取得できます。

于 2009-11-03T19:04:00.660 に答える
2

この問題には、パワー ダイアグラムと呼ばれるものを使用した効率的な解決策があります。ただし、これは非常に難しい数学であり、私がすぐに取り組みたいものではありません。「簡単な」解決策については、ラインスイープ アルゴリズムを調べてください。ここでの基本原則は、図をストリップに分割することです。各ストリップの面積の計算は比較的簡単です。

そこで、すべての円をこすり落としていない図に、円の頂点、円の底、2 つの円の交点のいずれかの位置に水平線を引きます。これらのストリップの内側では、計算する必要があるすべての領域が同じに見えることに注意してください。2 つの側面が円形セグメントに置き換えられた「台形」です。したがって、そのような形状を計算する方法を考え出すことができれば、すべての個々の形状に対して計算を行い、それらを足し合わせるだけです。この単純なアプローチの複雑さは O(N^3) です。ここで、N は図の円の数です。巧妙なデータ構造を使用することで、このライン スイープ メソッドを O(N^2 * log(N)) に改善できますが、本当に必要でない限り、おそらく問題に値するものではありません。

于 2010-01-21T15:57:42.930 に答える
1

解決しようとしている問題によっては、上限と下限を取得するのに十分な場合があります。上限は簡単で、すべての円の合計です。下限には、円が重ならないように単一の半径を選択できます。それを改善するには、各円の最大半径 (実際の半径まで) を見つけて、重ならないようにします。P_a が円 A の中心、P_b が円 B の中心、r_a が A の半径である場合、完全に重なり合った円を削除するのも非常に簡単です (そのような円はすべて |P_a - P_b| <= r_a を満たします)。 ) そして、これは上限と下限の両方を改善します。すべての円の合計だけでなく、任意のペアでペア式を使用すると、より良い上限を取得することもできます。「最高」を選ぶ良い方法があるかもしれません

上限と下限が与えられれば、モンテカルロ法をより適切に調整できるかもしれませんが、具体的なことは何も思いつきません。別のオプション (これもアプリケーションによって異なります) は、円をラスタライズしてピクセルをカウントすることです。基本的には、固定分布のモンテカルロ アプローチです。

于 2009-11-03T14:49:29.963 に答える
1

ピクセル ペインティング アプローチ (@Loadmaster によって提案されている) は、さまざまな点で数学的ソリューションよりも優れています。

  1. 実装ははるかに簡単です。上記の問題は、この JSFiddle ソリューションが示すように、100 行未満のコードで解決できます(ほとんどの場合、概念的にはるかに単純であり、処理するエッジ ケースや例外がないためです)。
  2. より一般的な問題に簡単に適応します。2D 描画ライブラリ (つまり、「すべて!」) でレンダリングできる限り、形態に関係なく、円、楕円、スプライン、ポリゴンなど、あらゆる形状で機能します。ビットマップ画像も。
  3. ピクセル ペイント ソリューションの複雑さは、数学的ソリューションの ~O[n*n] と比較して ~O[n] です。これは、形状の数が増えるほどパフォーマンスが向上することを意味します。
  4. また、パフォーマンスについて言えば、ほとんどの最新の 2D ライブラリ (HTML5 のキャンバスなど) はレンダリング作業をグラフィック アクセラレータにオフロードするため、多くの場合、ハードウェア アクセラレーションを無料で利用できます。

ピクセル ペインティングの欠点の 1 つは、解の精度が有限であることです。ただし、状況に応じて、より大きなキャンバスまたはより小さなキャンバスにレンダリングするだけで調整できます。また、2D レンダリング コードのアンチエイリアシング(多くの場合、デフォルトでオンになっています) により、ピクセル レベルよりも優れた精度が得られることにも注意してください。したがって、たとえば、100x100 の図を同じサイズのキャンバスにレンダリングすると、1 / (100 x 100 x 255) = .000039% のオーダーの精度が得られるはずです...これはおそらく「十分」です最も要求の厳しい問題を除くすべての場合。

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>

// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);
于 2013-05-27T14:53:03.360 に答える
1

役に立つかもしれないこのリンクを見つけました。ただし、決定的な答えはないようです。 Google が回答します。3 つの円のもう 1 つの参考文献は春樹の定理です。そこにも紙があります。

于 2009-11-03T13:34:36.137 に答える