マーチング スクエア(マーチング キューブに関連する) アルゴリズムをアイソ プレーン上で実行し、データを三角形のメッシュに変換しています。
これは機能しますが、非常に複雑なメッシュ データが作成されます。以下に示すように、これを必要最小限の三角形に単純化したいと思います。
輪郭をループしてみました (ポイント -> セグメント -> ポイント -> ...) が、ポイントに 2 つ以上の接続セグメントがある場合、輪郭が反転する可能性があります。
実行時に実行できるように、ソリューションはかなり高速であることが理想的です。私が使用している言語は C# ですが、おそらく他のほとんどの C ライクな言語から移植できます。
これは、3D コンピュータ グラフィックスでは非常に一般的な問題です。この問題を解決するアルゴリズムは、メッシュ単純化アルゴリズムと呼ばれます。ただし、サーフェス法線を考慮する必要がないため、2D の場合は問題を解決するのがはるかに簡単です。
最初に重要なことは、メッシュを変更する操作を提供する、信頼できるメッシュ データ構造を持つことです。任意のメッシュを生成および変更できる一連の操作は、たとえば「オイラー オペレータ」のセットです。
2D メッシュを単純化するには、2D メッシュの高密度バージョンを提供します。各クワッドを対角線で分割することにより、クワッド メッシュを三角形メッシュに簡単に変換できます。
密な三角形メッシュ:
次に、境界にない最短のエッジを繰り返し折りたたみます。「エッジの崩壊」は、次に示す典型的なメッシュ操作です。
いくつかのステップの後、メッシュは次のようになります。
(上記の回答で提案されているように) マーチング スクエアによって生成されたメッシュを単純化することは、非常に非効率的です。スカラー フィールド (ビットマップなど) からポリゴンを取得するには、最初に、ポリゴンの輪郭のみを生成するマーチング スクエアの修正バージョンを実行する必要があります (つまり、ジオメトリを生成しないマーチング スクエアの 16 のケースでは、ポイントを追加するだけです)。その後、三角測量アルゴリズム (例: Delaunay または Ear Clipping) を実行します。
編集:結果の輪郭に耳クリッピングを使用します。
http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
即時のステップでそれを行い、ボリューム表現からグリッド表現に進みます。
その後、ケース 3、6、9、12 の領域をより大きな/より長いバージョンにグループ化できます。
正方形をより大きな正方形にグループ化することもできますが、これは NP 問題であるため、理想的な最適化には長い時間がかかる可能性があります。
その後、ポリゴン バージョンに変換できます。
ポリゴンに変換した後、エッジを融合できます。