非凸ポリゴンに大きな一連の頂点を考えると、エッジを見つけるにはどうすればよいですか?
質問
一連の頂点(Aと呼ばれる)があり、この境界頂点セットが形状の輪郭になるように、すべての境界頂点を見つけたいと思います。
Aの頂点の多くは、形状の中にあるため、冗長です。これらの頂点を取り除きたいです。
私の質問はに似ています 頂点のエッジ(ポリゴン)を見つけるのに最適なアルゴリズム しかし、私はそれが非凸多角形のケースで働く必要があります。
編集:説明:以下の画像は凹面ポリゴンです。これは私が非凸の意味です。凸式ハルアルゴリズムを実行しても、ポリゴンの凹状の部分を保存しません(間違っていない限り)。
ポリゴンの内側と境界線に一連の頂点があります。
他のヒント
これは古い、おそらく放棄された質問ですが、それについて考えています。凸型の船体を探しているのではなく、ポリゴンの形状を維持したいのですが、線に沿って「エッジ」の間にあるポイントを取り除きます。
解決策は、隣接するポイントを踏み出し、1番目と2番目の線形勾配を計算し、その勾配値を保存し、PT1-PT2の勾配がPT2-PT3の勾配と等しい場合、2番目と3番目の勾配を計算することです。その後、PT2はラインの形成に冗長であるため、削除できます。 PT1に戻るまで、ループを続けてください。
これにより、凹状の形状が維持されますが、無関係な追加ポイントが削除されます。
あなたが探している用語はです 凹面船体.
問題の最も単純な形式は、凸型の船体のように明確に定義されていません。なぜなら、与えられたポイントをカバーする凹面ポリゴンは一意ではないからです。しかし、多くの良いアプローチがあります。
最も簡単なアプローチの1つは、ギフトラッピングアルゴリズムを使用するが、検討する各ステップでのすべてのポイントを検討する代わりに、 k- 現在の頂点の最小の隣人。
ここ k あなたのハイパーパラメーターは調整する必要があります。もしも k 高すぎると、凸型の船体が得られます。もしも k あなたが低すぎると、結果として得られるポリゴンには多くの凹面があります。
ここにいくつかの関連するリンクがあります:
- https://github.com/mapbox/concaveman
- https://gis.stackexchange.com/questions/1200/what-are-definition-algorithms-and-practical-solutions-for concave-hull
- concave船体:一連のポイントで占める領域の計算のためのk-nearest Neighborsアプローチ(リンク)