境界上のポリゴンのすべての点を取る凹状の船体

Question

私の研究では、ある境界の点群をランダムに囲む必要があります。凸形の船体は余分なスペースを取っていましたが、きつい形状ではありませんでしたので、次のようにしてエッジを緩和するように修正しました：i）与えられた点数の凸包を描きます。

ii）今度は各点についてではなく、凸包の境界チェックで、境界に追加できるかどうかをチェックします（もちろん、境界整形を変更します）。多角形。 （ポリゴンアルゴリズム内のポイント）

iii）すべてのポイントがポリゴンの内側にある場合、他のポイントではステップ2を繰り返します。

iv）境界にポイントを追加できない場合は、停止します。

ここで問題は、サンプルテストセットであり、すべてのポイントが境界に含まれています。私の疑問は次のとおりです。

i）これは凹型の船体ですか？

ii）与えられた点を反時計回りの順番に並べ、最初に凸包を描画するのではなく、すべての点を描画してポリゴンを描くだけの場合とはどのように違いますか？

iii）与えられた数の点について、すべての点がポリゴンの境界にくるように、非自己交差ポリゴンを描画することは可能ですか？あなたは、（それだけで2Dを説明し、可視化する方が簡単です！それはNDことができます）あなたは、2D多面体に興味があると仮定すると、

Answer 1

あなたが探している '非支配的な（non-dominated）'船体をもたらすポイントのセットの4つのPareto frontiersを見つける必要があります。なぜ4つのフロンティア？あなたは完全に多面体のエッジを定義するために4つのフロンティア（最小対最大、最大対分、最小対最大、および最小対max）を必要とするノート

以下の例を考えてみましょう。さらに、船体が凸であるかどうかは、あなたのポイントによって決まることに注意してください。上の例は、凸ではなく、連続ではないフロンティアを示しているため、ポリトープは凸ではなく連続でもありません。 4つのパレートの境界のセットは完全なポリトープの形状を構成します。

これを自分で実装しようとしているのであれば、あまりにも悪くなく、各点をそれぞれの点と比較して軸を比較し、両方の軸を好都合な方向に進める点を判断する必要があります。これをペアワイズ比較と呼びます。

C++ですでにコード化されたソリューションで、これはhttps://github.com/kevinduh/pareto