いくつかの凸多角形が点のSTLベクトルとして保存されています（多かれ少なかれ）。それらを非常に迅速に、できればかなり均等なサイズのピースに、「スライバー」なしでテッセレーションしたいと思います。
これを使用して、いくつかのオブジェクトを小さな断片に分解します。ポリゴンをテッセレーションする（小さな凸多角形または三角形のメッシュに分割する）ための優れたライブラリを知っている人はいますか？
すでにオンラインで見つけたものをいくつか見てきましたが、それらをコンパイルすることすらできません。これらのアカデミックタイプは、使いやすさをあまり考慮していません。
CGALには、この問題を解決するためのパッケージがあります。おそらく、 2Dポリゴンパーティショニングパッケージを使用するのが最善でしょう。たとえば、ポリゴンのyモノトーンパーティションを生成すると（非凸ポリゴンでも機能します）、次のようになります。
実行時間はO（n log n）です。
使いやすさの観点から、これはランダムなポリゴンを生成し、それを分割する小さなサンプルコードです（この手動の例に基づく）：
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を使用している場合は、インストーラーを使用してプリコンパイル済みライブラリを取得できます。このページには、すべてのプラットフォームのインストールガイドがあります。インストールは最も簡単ではないかもしれませんが、そこにある最も使用された堅牢な計算幾何学ライブラリを入手できます。cgalメーリングリストは質問に答えるのに非常に役立ちます...
poly2triは、2DDelaunay三角形分割用の非常に優れた軽量C++ライブラリのように見えます。
上記のコメントでbalint.miklosが述べたように、Shewchukの三角形のパッケージは非常に優れています。私は何度もそれを使用しました。プロジェクトにうまく統合され、triangle ++ C++インターフェースがあります。スライバーを避けたい場合は、三角形が（内部の）シュタイナーポイントを追加できるようにして、高品質のメッシュ（通常は制約付きの適合ドロネー三角形分割）を生成します。
GCAL全体をアプリに組み込みたくない場合は、おそらくこれを実装する方が簡単です。
http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
これと同じ問題を調査し始めたばかりで、ボロノイ分割を検討しています。元のポリゴンは、ボロノイセルの中心となる半ランダムなポイントの散乱を取得します。これらのポイントがより均等に分散されると、セルのサイズはより規則的になりますが、完全なグリッドに配置しないでください。そうしないと、内部のポリゴンになります。すべて同じに見えます。したがって、最初に、これらのセルの中心点を生成できるようにする必要があります。ソースポリゴンの境界ボックス上にそれらを生成することで、内部/外部のテストはそれほど難しくありません。
ボロノイエッジはこの写真の点線であり、ドロネー三角形分割の一種です。すべての鋭い三角形のポイントが鈍くなります。
Boostにはいくつかのボロノイ機能があります： 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は引き続き維持されますが、ピクセルで動作し、頂点やエッジポリゴンデータ構造ではなくピクセル出力を生成しますが、私のニーズには十分かもしれません。
詳細がわかったら、これを更新します。
必要な入力と出力についてもう少し詳しく説明すると役立つ場合があります。
たとえば、ポリゴンを三角形にしようとしているだけの場合は、三角形のファンが機能する可能性があります。ポリゴンを小さな断片にカットしようとしている場合は、ある種のマーチングスクエアを実装できます。
さて、私は悪い仮定をしました-マーチングキューブはマーチングキューブにもっと似ていると思いました。それはまったく異なっており、私が意図したこととはまったく異なります。：|
いずれにせよ、あなたの質問に直接答えるために、私はあなたが探していることをする簡単なライブラリを知りません。CGALの使いやすさについては同意します。
私が考えていたアルゴリズムは、基本的にポリゴンを線で分割することでした。線はグリッドであるため、ほとんどの場合、四角形になります。多角形の線の交点がある場合、実装は簡単です。この問題を引き起こす別の方法は、2Dポリゴンを関数のように扱い、ポイントのグリッドをオーバーレイすることです。次に、マーチングキューブに似た操作を行います。4つのポイントすべてがポリゴンにある場合はクワッドを作成し、3つが三角形を作成する場合、2つが長方形を作成するなどです。おそらくやり過ぎです。少し不規則に見えるポリゴンが必要な場合は、グリッドポイントの位置をランダム化できます。
一方、キャットマルクラークスタイルの細分割を行うことはできますが、スムージングは省略します。アルゴリズムは基本的に、図心と各エッジの中点にポイントを追加することです。次に、元のポリゴンの各コーナーに対して、コーナーの前のエッジの中点、コーナー、次のエッジの中点、および図心を接続する新しい小さなポリゴンを作成します。これによりスペースが並べて表示され、入力ポリゴンと同様の角度になります。
したがって、多くのオプションがあり、ブレインストーミングソリューションが好きですが、これを何に使用する予定かはまだわかりません。これは破壊可能なメッシュを作成するためですか？より小さな要素を必要とするある種のメッシュ処理を行っていますか？グーローシェーディングアーティファクトを回避しようとしていますか？これは前処理またはリアルタイムとして実行されるものですか？正確さはどれほど重要ですか？より多くの情報はより良い提案につながるでしょう。
凸多角形があり、品質にあまりこだわっていない場合、これは本当に簡単です-耳のクリッピングを行うだけです。心配しないでください。凸多角形の場合はO（n ^ 2）ではありません。これを素朴に行うと（つまり、耳を見つけたらクリップする）、三角形のファンができます。これは、スライバーを避けようとしている場合は少しドラッグになります。三角測量を改善できる2つの簡単なヒューリスティックは次のとおりです。
耳のクリッピングに基づいたより堅牢な三角測量器が必要な場合は、FISTを確認してください。