1

ランダムな位置に（接続された頂点のリストとして）複数の円があります。

円が交差すると、閉じた領域が作成されます (ベン図のようにhttp://en.wikipedia.org/wiki/Venn_diagram )

これらすべての領域の個別のポリゴンを生成するにはどうすればよいですか? 目標は、次の例のように、すべての領域を個別のポリゴンで色付けできるようにすることです。

ここに画像の説明を入力

ここに画像の説明を入力

反復ブール交差演算で一般的な解決策は可能ですか?

編集

次の簡単な抜粋は、[NodeBox](http://nodebox.net/code/index.php/Home)交差する楕円を描画するスクリプトです。

oval(x0,y0,w,h)楕円を作成します。

docによると、次のようなパスのブール演算p[19].difference(p[17])は「フラット」な結果をもたらします (「多数の直線セグメントで構成される」)。

パスの座標を追加または変更できます。 

size(500, 500)

p = []
s = 54
nofill()
stroke(0)
for k in xrange(10):
    w  = 10+k*s/2
    w2 = 10+k*s 
    h = 10+k*s
    h2= 10+k*s
    p.append( oval(WIDTH/2 - w/2, HEIGHT/2 - h/2, w,  h, draw=False))
    p.append( oval(WIDTH/2 - w2/2, HEIGHT/2 - h2/2, w2, h2, draw=False))


cp = p[19].difference(p[17]).intersect(p[18], flatness = 0.3)

for pi in p:
    drawpath(pi)

fill(color(1,0,0))
drawpath(cp)
4

1 に答える 1

3

言語にとらわれないとおっしゃったので、そのようにお答えします。提案どおりに、ポリゴンのブール演算で必要なものを取得できます。F が交差しない多角形のセットであり、P が 1 つ以上の F と重なる新しい多角形である場合、次のようにします。

Let p = P
for each polygon f in F
  Replace f by f-p and intersect(f, p).
  Set p = p-f
end
add p to F

アイデアは、新しいポリゴン p を使用して、F 内の既存の「フラット」ポリゴンを p と共有され、p と共有されない部分に分割し、元のポリゴンとのオーバーラップを p 自体から削除して続行することです。すると、p に残っているのは F と何も重なっていない部分なので、それを新しい多角形として F に追加します。

したがって、円形ポリゴンのランダムなコレクションを処理するには、そのうちの 1 つを含む F から開始し (これは確かにフラットなコレクションです!)、完了するまで一度に 1 つずつ追加します。

実際には、これはカスタム アルゴリズムよりも効率が著しく低下します。このような問題を処理する標準的な方法は、スイープ ラインです。技術。円の上を左から右に掃引する垂直線を想像してください。円に「触れる」と、多角形の構築が開始されます。交差点に触れると、1 つのポリゴンが閉じ、2 つのポリゴンが続き、新しいポリゴンが開きます (通常の場合)。円の右端に到達すると、関連するポリゴンが閉じます。「閉じた」ポリゴンがスイープ ラインから削除され、出力リストに追加されます。スイープ ライン アルゴリズムは概念的には難しいものではありませんが、特殊なケースが多いため実装が面倒です (特に、スイーパーに平行なラインの場合や、1 つのポリゴンの頂点が別のポリゴンのエッジ上にある場合など)。ただし、これらを解決するための一般的な手法は単純化のシミュレーションです。）。

「一般化された配置」は、このような問題を説明するために使用される計算幾何学の用語です。一般化された配置は、線、セグメント、および/または多角形の集まりです (通常の配置は線のセットです)。たとえば、一般化された配置の CGAL ライブラリは、まさにあなたの問題を高い効率で実行できます。CGAL は C++ の大規模な汎用ライブラリであるため、学習コストが多少かかります。商用目的のライセンスは扱いにくいものです。

于 2013-12-21T17:37:57.650 に答える