凹多角形の境界上にある一連の点があります。これらの点を頂点とする非交差ポリゴンを1つ見つけたいと思います。つまり、凹多角形の頂点をccw（またはcw）で並べ替えたいと思います。
ポリゴンがccwまたはcwのどちらの方法で順序付けられているかを評価する方法を調べました（外積の計算と合計）。正確には私の問題ではありません。頂点がランダムな順序であり、ポリゴンのクラストにcwまたはccwになるように並べ替えたいと思います。
頂点の最初のシーケンスを取得し、交差点を連続して特定することを考えました。初期点シーケンスが[x1、y1;の場合 x2、y2; x3、y3; ...]そして2番目と3番目のポイントが交差しているので、シーケンス[x1、y1;を続行します。x2、y3; x3、y2; ...]
どのようなアルゴリズムを思いつくことができますか？背後にある概念は何ですか？いくつかの参考資料にヒントがありますか？
Regds
私が問題を正しく理解していれば、凹面ポリゴンの可能性がある時計回りの順序でポイントの入力セットを並べ替えることができます。これは次のように解決できます。
p1 と p2 を左端と右端の点とします。点の下凸包 S を見つけます。S には、p1、p2、および線 p1p2 の下にあるすべての凸包点が含まれます。残りのポイント (S にないポイント) を x 座標で並べ替えます。この並べ替え順序と S の順序 (下凸包アルゴリズムによって生成される) を組み合わせることで、すべての頂点の望ましい時計回りの順序が得られます。
多角形が作成された時点で、多角形が凹面多角形である可能性のある点のセットよりも適切に定義されていない限り、使用する必要がある情報があります。
たとえば、頂点がシェイプまたはイメージから取得された場合、シェイプ内の塗りつぶされたピクセルが役立ちます。あるプロジェクトでは、ブロブの周囲に点を並べる必要があるため、ブロブの境界ピクセルを取得し (さまざまな方法で実行できます)、それらを DFS スタイルのトラバーサルを使用して順番に配置します。次に、エッジをマージし、ジャンクションで決定を下すアルゴリズムを作成しました。