7

平面上で「N」個の円盤/円の交点/和集合を見つける問題は、1978年の論文でMIShamosによって最初に提案されました。

シャモス、ミシガン州「計算幾何学」博士号 論文、イェール大学、ニューヘブン、コネチカット州1978年。

それ以来、1985年に、Micha Sharirは、ディスク交差/和集合問題（修正ボロノイ図に基づく）のO（n log2n）時間およびO（n）空間決定論的アルゴリズムを提示しました。平面ディスクのセット。SIAM.J計算。14（1985）、pp.448-468。

1988年、Franz Aurenhammerは、パワーダイアグラム（ボロノイダイアグラムの一般化）を使用した円の交差/和集合のためのより効率的なO（n log n）時間とO（n）空間アルゴリズムを発表しました：Aurenhammer、F.パワーを使用したディスクとボールのアルゴリズムの改善ダイアグラム。Journal of Algorithms 9（1985）、pp.151-161。

1983年の初めに、Paul G. Spirakisは、O（n ^ 2）時間決定論的アルゴリズム、およびO（n）確率的アルゴリズムも発表しました。担当者98、部門計算。Sci。、Courant Institute、ニューヨーク大学、1983年。

計算幾何学パッケージに焦点を当てて、上記のアルゴリズムの実装を探していましたが、まだ何も見つかりませんでした。どちらも実践するのは簡単ではないように思われるので、誰かが私を正しい方向に向けることができれば、それは本当に素晴らしいことです！

おそらく、Constructive Solid Geometry（CSG）パッケージには、円プリミティブをオーバーラップさせるための表面積機能がありますか？

4

2 に答える 2

6

私は、ボールのセットの和集合を計算するためのアルゴリズムを調べることに時間を費やしました-あなたが言うように、それは一般化されたボロノイ図を使用して行われます。

CGALライブラリには、ボールの結合を実装するパッケージがあります。これは、関心のあるものより1次元高く、交差点を処理しません。おそらく葉巻はありません。

2次元で作業している場合、問題は3次元で凸包を見つけることと同じです。CGALまたは別のパッケージの凸包を使用できます。

あなたが言及した特定のアルゴリズムの実装を探しているなら、私はあなたを助けることができません。ただし、和集合と交差を簡単に計算できるパワーダイアグラムを見つけたいだけの場合は、3D凸包アルゴリズムを使用して独自にロールする方が簡単な場合があります。

中途半端な答えで申し訳ありませんが、どこかから始めて、どれだけの柔軟性があるかを確認することもできます。

編集： 2Dパワーダイアグラム用のCGALパッケージもあります：http ：//www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html 。

また、@ RGreyは、 http：//www.cgal.org/Manual/3.5/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.htmlで、一般化されたポリゴンの2Dブール値を計算するためのCGALライブラリを見つけました。

于 2010-05-18T03:48:10.617 に答える
1

CGALには2D電力図の実装はありません。上記のリンク（http://www.cgal.org/Manual/last/doc_html/cgal_manual/Apollonius_graph_2/Chapter_main.html）は、euclid ^2+の代わりにeuclid+重みを使用する加法加重ボロノイ図用です。重量（パワーダイアグラムと同様）。

于 2011-08-08T15:20:33.233 に答える