私は一連の頂点(Aと呼ばれる)を持っており、この境界頂点セットが形状の輪郭になるように、すべての境界頂点を見つけたいと考えています。
A の頂点の多くは形状の内側にあるため冗長です。これらの頂点を取り除きたいと思います。
私の質問は、頂点のエッジ (ポリゴン) を見つけるための最適なアルゴリズムに似ていますが、凸でないポリゴンの場合に機能する必要があります。
編集: 明確化: 下の画像は凹面ポリゴンです。これは、私が非凸で意味したものです。それに凸包アルゴリズムを実行すると、ポリゴンの凹面部分は保持されません(間違っていない限り)。
ポリゴンの内側と境界線上に一連の頂点があります: [[x1,y1], [x2,y2]...] 頂点が形状の境界線の輪郭だけになるように、セットを減らしたいと思います。
これはホットな話題のようです.. https://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions
この紙が一番良さそうです。 Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008) 平面内の一連の点の形状を特徴付ける単純な多角形の効率的な生成。パターン認識 v41、3224-3236
あなたの説明はやや曖昧ですが、一連の点の凸包を構築するアルゴリズムを探している可能性があります。簡単に言えば、凸包は、すべての頂点の周りに輪ゴムを置いた場合に得られる形状です。2D で凸包アルゴリズムを記述することはそれほど難しくなく、 qhull
のようにそれを行うライブラリがいくつかあります。
（その答えは、あなたがリンクしている質問にも記載されていますが、これはあなたの質問の特別なケースのようです）
これは古い、おそらく放棄された質問ですが、考えさせられました。凸包を探しているのではなく、ポリゴンの形状を維持したいのですが、線に沿った「エッジ」の間にあるポイントを取り除くだけです。
解決策は、隣接するポイントをステップスルーして、1 番目と 2 番目の線形勾配を計算し、その勾配値を保存して、pt1-pt2 の勾配が pt2-pt3 の勾配と等しい場合、2 番目と 3 番目の勾配を計算することです。 pt2 は行を形成する上で冗長であるため、削除できます。pt1 に戻るまでループを続けます。
これにより、凹面の形状が維持されますが、無関係な余分なポイントが削除されます。