algorithm - 複数のポリゴンの共通のアウトラインを見つける

Question

複数のポリゴン間で共通のアウトラインを描画するためのアルゴリズムを見つけようとしています。私が言いたいのはこの写真のようなものです：

2つの長方形（私の場合は長方形ではなく、ほとんどの角度が直角のポリゴン）があり、画像の2番目の部分にある赤いパスのような一般的なアウトラインを探しています。私が見ている最大の問題は、画像の2番目の部分で黄色でマークした新しいポイントを見つけることです。ポリゴンが交差したり、ポリゴン自体に接触したりすることはありません。ポリゴンをポイントとして反時計回りに格納しています。

私はグーグルするべきいくつかの手がかり、ソース、あるいはキーワードさえ探しています、それは私の仕事を少し簡単にするかもしれません...

編集：凸包のようなものですが、頂点ではなくエッジを見ると、黄色の点はおそらくエッジの連続にあります。

EDIT2：わかりました、ポリゴンの周りに指定されたサイズの境界線を描画する必要がありますが、2つのポリゴンが境界線のサイズよりも近い場合、共通の境界線があります。これは、の「内側」の部分がない2つの境界線の合計のようなものです。それとこの2つのポリゴンは1つの形状として扱われます。だから私はその周りにこの境界線を描くために使用されるこの赤いポリゴンを見つけようとしています。

Answer 1

ポリゴン（黄色の頂点）に頂点を追加することから始めます。これは、すべてのエッジを無限に拡張された他のすべてのエッジに対してクリップすることによって行います（たとえば、エッジを無限の線に変えます）。

新しい頂点を拡張エッジに接続します。これにより、ポリゴンメッシュが作成されます。

ここでトリックが来ます：

開始条件：

• 左上の頂点を選択してください。存在できるのは1つだけです。

• 1で見つかった頂点に接続し、右に伸びる勾配が最小のエッジを選択します。このエッジは常に最終的なポリゴンの周囲にあります。

反復：

• 現在のエッジから、時計回りに他のエッジに沿って歩きます。これを行うと、新しい頂点に遭遇し、これらの頂点が他の複数のエッジに接続する可能性があります。常に最も反時計回りのものを選び、続行します。これにより、常に最終的なポリゴンの周囲にとどまります。

終了条件：

• 左上の頂点に再び到達したらすぐに停止します。

おめでとうございます。ポリゴンの外縁を歩き回ったところです。

Answer 2

http://www.comp.nus.edu.sg/~tancl/Papers/DAS06/39-oyuanbuusu.pdfのように「最適なバウンディングボックス」を探します。もちろん、その参考文献を再帰的に探します。 。