線分でパーツにスライスする必要がある単純な多角形 (凸面または凹面で、穴はありません) があります。スライス後に生成されるポリゴンの数を実際に決定する方法や、頂点をグループ化する方法がわかりません。
常に 2 つのサブポリゴンになる基本的な凸型のケースは簡単ですが、複雑な凹型の形状はどのように処理すればよいでしょうか? たとえば、「E」形状のポリゴンを考えてみましょう。垂直スライスは 4 つのポリゴンを生成できます。これらのサブポリゴンのそれぞれを構成する頂点を特定するにはどうすればよいですか?
ポリゴンの定義: ここには 2 つのオプションがあります。私のポリゴンは、頂点の順序付きリストにすることも、三角形の配列にすることもできます。三角形の配列を使用するソリューションをお勧めします。すべての三角形をループして、交差する場合は線でスライスするのは非常に簡単です。しかし、それらの三角形を結果として得られるサブポリゴンにグループ化する方法がわかりません。
疑似コードや一般的なアドバイスでも構いません。C# 実装が理想的です。
しばらく前に、私はこの答えをやや異なる質問に与えました。
その答えは、その形状の三角形分解が与えられた場合に、形状の輪郭を確立する方法を提供します。
基本的な考え方は、すべての三角形のエッジを有向ベクトルと見なし、等しいが反対側のエッジをキャンセルすることです。
あなたの場合、元の形状を表す三角形がたくさんあります。個々の三角形を線でスライスします。次に、スライスされたエッジがキャンセルされないという条件で、上記で概説した方法を使用して三角形を形状に再収集します。
上記の回答に詳細と写真があります。しかし、手順を要約すると、
三角形の分割を実行します
結果の三角形ごとに、3 つの有向エッジをセットに追加します。時計回りの順序を確認するには、この質問への回答を確認してください。
エッジ セットを調べて、等しいが反対のエッジのペアを削除します (それらがスライス エッジでない場合)。
セット内のエッジを選択し、テールが最初のエッジのヘッドと一致するエッジを見つけます。次に、開始エッジに到達するまで、そのエッジに対して繰り返します。エッジ セットに到達したら、エッジ セットから各エッジを削除します。開始エッジに到達すると、結果のポリゴンの 1 つを表す閉じたループができます。
エッジがなくなるまで手順 4 を実行します。
これらはすべて、ポリゴンの三角形分割から開始するという希望に対応します。ただし、元の質問に対するコメント者の 1 人が指摘したように、カット ポリゴンから新しいポリゴンを生成する (2D)に示されている代替案を検討することをお勧めします。