私は凸包アルゴリズムを使用して、不規則な形状の輪郭を見つけました。それは十分ではありませんが...
おそらく、私が持っている形状が凸状であるとは保証できないためです...
一連の長方形があり、輪郭の外側にあるすべての点を取得できるようにしたいのですが、輪郭の点を捨てないようにします。
凸包アルゴリズムはうまく機能しますが、右の例のように機能するため、輪郭に関する情報が失われます。
左のバージョンに近く、外側のコーナーを保持し、内側のポイントのみを削除するものが必要です...
そのようなアルゴリズムはありますか？
または、このような形状 (ポリゴン) を凸形状に分割して、凸包アルゴリズムが適切に処理できるようにする方法はありますか?
リンクからリンクへと、Hertel-Mehlhorn Algorithm のようなある種のアルゴリズムを設定する方法を見つけようとしてきましたが、この状況で交差する線がどのように使用されるかはわかりません...
ご提案ありがとうございます。
非凸多角形が示したとおり (つまり、四角形要素の集合) である場合、境界上にある四角形のエッジを見つけるだけです。
これは、これらの「外部」エッジは 1 つの要素にのみ表示され、「内部」エッジは 2 つの隣接する要素に共通であることに注意することで実現できます。これは、次の単純なアルゴリズムを意味します。
edge_list = {}
for (i = all elements in mesh)
for (j = all edges in element(i))
edge_list <- push jth edge of ith element
endfor
endfor
edge_list <- sort
edge_list <- remove_duplicates
残りの一意のエッジは、ポリゴンの外側の輪郭を形成します。この単純なアルゴリズムはO(N*log(N))時間内に実行されます。
エッジの比較に適切なハッシュ テーブルを使用することで複雑さを改善し、複雑さをO(N).