非凸ポリゴンに大きな一連の頂点を考えると、エッジを見つけるにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/2741589

質問

一連の頂点（Aと呼ばれる）があり、この境界頂点セットが形状の輪郭になるように、すべての境界頂点を見つけたいと思います。

Aの頂点の多くは、形状の中にあるため、冗長です。これらの頂点を取り除きたいです。

私の質問はに似ています 頂点のエッジ（ポリゴン）を見つけるのに最適なアルゴリズム しかし、私はそれが非凸多角形のケースで働く必要があります。

編集：説明：以下の画像は凹面ポリゴンです。これは私が非凸の意味です。凸式ハルアルゴリズムを実行しても、ポリゴンの凹状の部分を保存しません（間違っていない限り）。

concave polygon

ポリゴンの内側と境界線に一連の頂点があります。

他のヒント

あなたの説明はやや曖昧ですが、あなたが構築するアルゴリズムを探している可能性があります 凸式船体 一連のポイントの。簡単に言えば、すべての頂点の周りに輪ゴムを置くと、凸式の船体が得られる形状です。
2Dで凸式ハルアルゴリズムを書くことはそれほど難しくなく、そのようなライブラリがいくつかあります QHULL

（その答えは、あなたがリンクしている質問にも与えられています。

これは古い、おそらく放棄された質問ですが、それについて考えています。凸型の船体を探しているのではなく、ポリゴンの形状を維持したいのですが、線に沿って「エッジ」の間にあるポイントを取り除きます。

解決策は、隣接するポイントを踏み出し、1番目と2番目の線形勾配を計算し、その勾配値を保存し、PT1-PT2の勾配がPT2-PT3の勾配と等しい場合、2番目と3番目の勾配を計算することです。その後、PT2はラインの形成に冗長であるため、削除できます。 PT1に戻るまで、ループを続けてください。

これにより、凹状の形状が維持されますが、無関係な追加ポイントが削除されます。

あなたが探している用語はです 凹面船体.

問題の最も単純な形式は、凸型の船体のように明確に定義されていません。なぜなら、与えられたポイントをカバーする凹面ポリゴンは一意ではないからです。しかし、多くの良いアプローチがあります。

最も簡単なアプローチの1つは、ギフトラッピングアルゴリズムを使用するが、検討する各ステップでのすべてのポイントを検討する代わりに、 k- 現在の頂点の最小の隣人。

ここ k あなたのハイパーパラメーターは調整する必要があります。もしも k 高すぎると、凸型の船体が得られます。もしも k あなたが低すぎると、結果として得られるポリゴンには多くの凹面があります。

ここにいくつかの関連するリンクがあります：

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top