C++ 2Dテッセレーションライブラリ？

Question

私はいくつかの凸多角形を点のSTLベクトルとして保存しています（多かれ少なかれ）。私はtessellateに、本当にすばやく、好ましくはかなり均等に大きめのものにしたいと思っています。

私はそれを使っていくつかのオブジェクトを小さな断片に分解します。誰もポリゴンを分割するための素敵なライブラリを知っていますか（それらをより小さな凸多角形または三角形のメッシュに分割する）？

私はすでにオンラインで見つかったいくつかを見てきましたが、コンパイルすることさえできません。これらの学術的なタイプは、使いやすさを重視していません。

Answer 1

CGALには、この問題を解決するパッケージがあります。おそらく2D Polygon Partitioningパッケージを使用するのが最善でしょう。たとえば、あなたは（だけでなく、非凸多角形のために働く）ポリゴンのyモノトーンのパーティションを生成することができ、あなたはこのような何かを得るでしょう：

y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif

走った時間はO（n個のログですn）。使いやすさの面では

これは（this manual exampleに基づいて）小さなサンプルコードのランダムなポリゴンを生成し、それを分割です：

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef CGAL::Partition_traits_2<K>       Traits; 
typedef Traits::Point_2          Point_2; 
typedef Traits::Polygon_2         Polygon_2; 
typedef std::list<Polygon_2>        Polygon_list; 
typedef CGAL::Creator_uniform_2<int, Point_2>    Creator; 
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator; 


int main() 
{ 
    Polygon_2 polygon; 
    Polygon_list partition_polys; 

    CGAL::random_polygon_2(50, std::back_inserter(polygon), 
         Point_generator(100)); 

    CGAL::y_monotone_partition_2(polygon.vertices_begin(), 
           polygon.vertices_end(), 
           std::back_inserter(partition_polys)); 

    // at this point partition_polys contains the partition of the input polygons 
    return 0; 
} 

CGALをインストールするには、Windows上にある場合は、インストーラを使用することができますプリコンパイルされたライブラリを入手し、すべてのプラットフォームのインストールガイドがthis pageにあります。インストールするのが最も簡単ではないかもしれませんが、最も使用されている堅牢な計算ジオメトリライブラリがあります。cgal mailing listは質問にお答えするのに非常に役立ちます...

Answer 2

ご希望の入出力役に立つかもしれない。

たとえば、ポリゴンを三角形にするだけであれば、三角形のファンが動作する可能性があります。多角形を小さなものにカットしようとするなら、ある種のマーチング・スクエアを実装することができます。

---

さて、私が悪いの仮定を作った - 私は行進の正方形がマーチングキューブに類似であろうと仮定しました。それは、全く違っていて、私が意味するものではないことが分かります。

いずれにしても、あなたの質問に直接答えるために、あなたが探している単純なライブラリはわかりません。私はCGALの使いやすさに同意します。

私が考えていたアルゴリズムは、基本的にラインがグリッドであるポリゴンを分割していたので、ほとんどが四角形になりました。ポリゴンラインの交差点があれば、実装は簡単です。この問題を引き起こす別の方法は、2dポリゴンを関数のように扱い、点のグリッドをオーバーレイすることです。キューブを行進させるのに似た何かをするだけです.4つのポイントがすべてポリゴンにあれば、クワッドを作ります.3つあれば三角形、2つは長方形などになるでしょう。多少不規則なポリゴンが必要な場合は、グリッドポイントの位置をランダム化することができます。

一方、catmull-clarkスタイルの細分化を行うことはできますが、スムージングは​​省略します。アルゴリズムは基本的に重心と各エッジの中間点にポイントを追加します。次に、元のポリゴンの各コーナーに対して、コーナー、コーナー、次のエッジの中間点、および重心の前のエッジの中間点を接続する新しい小さなポリゴンを作成します。これはスペースをタイルし、入力ポリゴンに似た角度を持ちます。

多くのオプションがありますが、私はブレーンストーミングソリューションが好きですが、これを使用するために何を計画しているのかはまだ分かりません。破壊的なメッシュを作成するのですか？小さな要素を必要とする何らかの種類のメッシュ処理を行っていますか？グーローシェイディングアーティファクトを避けようとしていますか？これは前処理またはリアルタイムで実行されるものですか？正確さはどれくらい重要ですか？より多くの情報がより良い提案につながります。

Answer 3

GCAL全体をアプリに組み込みたくない場合は、実装する方が簡単でしょう。上記のコメントで述べたようbalint.miklos

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 4

、Shewchukのtriangleパッケージはかなり良いです。私はそれを何度も使ってきました。プロジェクトにうまく統合され、triangle++ C++インターフェイスがあります。スライバーを避けたい場合は、三角形にスタイナーポイントを追加して、高品質のメッシュ（通常は拘束適合の派生三角形分割）を生成できるようにします。

Answer 5

凸多角形を使用していて、品質があまり上がらない場合は、これは本当に簡単です。ear clippingを実行してください。心配しないでください。凸多角形の場合はO（n^2）ではありません。これを馬鹿にすると（つまり、耳を見つけたときに耳を掴む）、三角形のファンが得られます。スライバを避けようとしている場合、これは少し難しいものです。三角測量を向上させることができる2つの些細な経験則は

1. ソートに耳あり、またはそれは遅すぎるかどう
2. は、ランダムに耳を選択してください。

耳のクリッピングに基づいてより頑丈な三角形を使用する場合は、FISTをチェックしてください。

Answer 6

poly2triは、2D Delaunay三角測量のための本当に素晴らしい軽量C++ライブラリのようです。

Answer 7

私はこの同じ問題を探し始めました。私はボロノイのテッセレーションを検討しています。元のポリゴンは、ボロノイセルの中心となるセミランダム点の散乱を受けます。より均一に分布すると、セルはより規則的なサイズになりますが、完全なグリッドには存在しないはずです。すべて同じに見えます。したがって、最初に、これらのセル中心点を生成することができます。ソースポリゴンの境界ボックス上にそれらを生成し、内部/外部テストはあまり難しくありません。

ボロノイエッジは、このピクチャの点線であり、デラウネイ三角測量の補数の一種です。全て鋭い三角形の点が平滑化になる： http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

は、次のステップは、ボロノイ多角形を作成している：

ブーストは、いくつかのボロノイ機能を有しています。 Voro ++ http://math.lbl.gov/voro++/は3D指向ですが、約2d構造が機能することは示唆されていますが、2Dボロノイ向けのソフトウェアよりもはるかに遅くなることがあります。ランダムな学術ホームページの孤児プロジェクトよりも優れていると思われる他のパッケージはhttps://github.com/aewallin/openvoronoiです。

OpenCVはこれらの行に沿って何かをサポートするように見えますが、廃止されました（しかしc-apiはまだ動作しますか？）。cv :: distTransformはまだ維持されていますが、ピクセル上で動作し、頂点とエッジポリゴンのデータ構造ではなくピクセル出力を生成しますが、私のニーズには十分であるかもしれません。

もう一度学んだことがありますが、これを更新します。