特定の点を囲む境界ポリゴンを決定する

Question

私は、ポリゴンに点だけが含まれるように、別の点の集合（集合B）から特定の点の集合（集合A）の周りの境界ポリゴンを決定する方法を見つけようとしています簡単にするために、多角形が凸であると仮定することができ、集合Aは2点しか含まず、解は与えられたデータから存在する。

例えば、 these pointsのように、赤い点から青い点の周りに多角形を作成したいとします。thisのようにします。これは、青い点をカットしないで最大の角度を持つ次の点を見つけることによって行うことができますが、私はthisのように結果が極端に小さくならないようにしたくありません。

この問題を解決するための提案やアルゴリズムはありますか？

Answer 1

すべての（赤と青の）点で三角測量を計算すると、青い頂点を含む三角形が必要な領域の最初の近似を形成するように見えます。この近似は通常は凹形であるため、「耳」をカットする必要があります。

結果が小さすぎると、外側の境界三角形の3番目の頂点が凸状に違反しない場合は追加することができます。