algorithm - 指定されたすべての点を通る凹多角形を作成する

Question

ポイントのセットが与えられた場合、これらのポイントを使用して、交差しない凹型ポリゴンを作成したいと考えています。凸包は凹部分を無効にしますが、x/y 座標または中心からの角度でそれらを配置すると、とがったアーティファクトが作成されます。これを行う簡単な方法はありますか？

作成したいポリゴンの例:

Answer 1

周囲の頂点しかなく、周囲の頂点間の距離が周囲のエッジ間の距離よりも小さくなることが保証できる場合は、最小スパニング ツリーを使用できます。

上の例は、MST が機能する場所を示しています (結果のポリラインの最初と最後の頂点が結合されています)。

下の例は、境界の端が近づきすぎるとどうなるかです。