algorithm - 点の集合を囲む多角形

Question

ポイントのセット S (2D : x と y で定義) があり、セットのすべてのポイントを囲む最小の (つまり、ポイントの数が最小の) P を見つけたいと思います。P は順序付けられたサブセットです。 S.

これを計算するための既知のアルゴリズムはありますか? (この分野における私の文化の欠如は驚くべきことです...)

ご協力いただきありがとうございます

Answer 1

この問題には多くのアルゴリズムがあります。これを「最小境界ボックス」と呼びます。特にここでは、「凸包」を検索しても解決策が見つかります。

1 つの方法は、一番左のポイントを見つけて、他のすべてのポイントが線分 p(n-1)p(n) の右側にあるポイントを検索することを繰り返します。

Answer 2

これが簡単な解決策です...

三角形を形成するために任意の 3 点から始めます。次の操作でポリゴンに各ポイントを追加します。

エッジを 2 つの連続したパスに分割します。一方のパスでは、各エッジの線が追加するポイントをポリゴンの残りの部分から分離し (これを「分離パス」と呼びます)、もう一方のパスでは各エッジの線を分割します。ポリゴンと同じ側に点があります。

(注: 形状が凸状のままである限り、これらの 2 つのパスは連続し、形状全体を形成します)

分離パスにエッジがない場合、ポイントはポリゴンの内側にあり、無視する必要があります。そうでない場合は、ポリゴンから分離パスを削除します。これを 2 つのセグメントに置き換えて、分離パスの各エンドポイントを新しいポイントに接続します。

タダ！:)

Answer 3

凸包アルゴリズムに関する優れたリソースは次のとおりです: The Convex Hull of a 2D Point Set or Polygon (Dan Sunday 著)

Answer 4

おそらく、凸包である最小の領域が必要であることを意味します。

本当に最小のポイントが必要な場合は、頂点位置が非常に大きい三角形を作成して、すべてのポイントを囲むことができます。