複数の点集合からの凸包の計算

Question

私は、グラフ理論が好きなら、サイクルを考える（思考サイクル）をしています。個々のフィーチャ/ポリゴンではなく、フィーチャコレクション全体の凸包を探したいと思います。私はモノトーン連鎖を使用することを考えていましたが、ポイントの単一のセットのために私にO(n log n)時間を与えるが、私はポイントの0からnのコレクションを持つことができるので、高速処理時間を達成するためにこれを行うための良い方法がある？

おかげ

Answer 1

あなたの多角形が凸であれば、rotating calipersの使用を検討してください。

その用途の一つは、あなたが何をしたいのかacheiveするには2通りの方法があります2つの凸多角形（より多くのポリゴンのマージ凸包を繰り返す）（chapter 5、chapter 2.6）

Answer 2

するための共通の凸包の構築されています。

最初の方法 "オンライン"凸包アルゴリズムを使用します。 「オンライン」とは、ポイントを1つずつ追加できるようにする（動的追加）を意味します。私はGitHubでアクセス可能な1ポイントあたりのO（log h）のアルゴリズムを実行しました。それは実際には最も高速です。それはOuellet Convex hullに基づいています。プロジェクトはOuelletConvexHullAvl2Onlineです。あなたの場合、それぞれのポリゴンの上をループし、それらのそれぞれについて、オンラインアルゴリズムを提供するそれぞれのポイントをループします。

使用例：

OuelletConvexHullAvl2Online.ConvexHullOnline convexHullOnline = new OuelletConvexHullAvl2Online.ConvexHullOnline(); 
       foreach (Point pt in points) 
       { 
        convexHullOnline.DynamicallyAddAnotherPointToConvexHullIfAppropriate(pt); 
       } 

       return convexHullOnline.GetResultsAsArrayOfPoint(); 

それはポイントのベクトル（IEnumerableをまたはポイント）の単一のインスタンスになるよう があなたのポリゴンをラップする「コンポジット」デザインパターンを使用して第二の方法。次に、通常のアルゴリズムにコンポジットオブジェクトを送ります。コンポジットは、すべてのポリゴンの各ノードを単一のオブジェクト（ポイントの配列のようなもの）であるかのように供給するという難しい作業を行います。ところで、クラスOuelletConvexHullAvl2Onlineのアルゴリズムでコンポジットを使用します：ConvexHullEnumeratorは、4象限（AVLツリー）に含まれる結果の凸包点を列挙します。