computational-geometry - エッジのセットからの最も外側のポリゴン

Question

すべて接続されている 2 次元の線分のセットがあるとします。セット内の最も外側のセグメントを見つけるアルゴリズムが必要です。つまり、同じ領域を区切る最小のサブセットです。

注: これは、セグメントを構成する点の凸包を見つけることと同じではありません。

編集: 一番上にセグメントの初期セットがあります。その下には、内側のセグメントが削除された同じアウトラインがあります。(小さな灰色の十字は無視してください。交点を示すためのものです。)

Answer 1

三角形化された非凸ポリゴンを指定すると、頂点のトラバーサルの方向 (反時計回り) を指定できます。すべての三角形を、その​​頂点の WRT トラバーサルと同様の向きにします。すべての三角形を有向辺に分解します。すべての三角形のすべてのエッジは、2 つの頂点のタプルです(a, b)。隣接する三角形ごとに、2 つの反対方向のエッジ(a, b)とがあり(b, a)ます。このようなエッジのペアは、今後の検討から単純に除外できます。最後に、排他的な外側エッジのセットを取得します。

ポリゴンが非単純な部分で構成されている場合でも、一般性が失われることはありません (ただし、頂点のトラバーサルの方向を指定することはできます)。

ソース セグメントで構築されたポリゴンの三角形分割は明らかな手順です。頂点を $d + 1$ 放物面と三角形分割に引き伸ばし、三角形を除外し、ソース セグメントに一致しないエッジを少なくとも 1 つ含みます。

もう 1 つの考えられるアプローチは、わずかに変更されたギフト ラッピング アルゴリズムです。

Answer 2

以下は、凸包から始まり、内側に向かって進むアプローチです。直観的には、船体のエッジから始めて、エッジ セットの最短パスをたどって、ギャップに「沿って」最も近いポイントを見つけてギャップを埋めます。

1. ポイントの凸包を計算します。
2. ハル セットをエッジ セットと交差させます。これにより、切断された可能性のある一連のエッジ パスが残ります。
3. 2 つのエッジを持たないポイント (つまり、グラフ用語で言えばリーフ) は、元のエッジ セットで最短パスを見つけることによって、最も近いリーフに接続されます。
4. 船体によって閉じられたときに最小の領域を作成するパスによって、任意のタイを破ることができます。