n 個の頂点を持つ単純な多角形 P1 があります。n は小さく、たとえば 8 です。この多角形は、2D ポイントのセットの周囲を表します。
次に、別のポリゴンがあります。これを P2 と呼びましょう。頂点の最大数も n です。P2 は P1 に近いため、P1 と P2 の領域を一緒に表す新しい多角形 P3 を描画することは理にかなっています。
新しいポリゴン P3 のポイントを選択するアルゴリズムを探しています。P1 + P2 の形状を可能な限り適切に記述したいと思います (それでも、n 個のポイントで!)。新しいポリゴン P3 の内側にあるポリゴンの作成に使用されるポイントの数は最大化されますが、 P3 はできるだけ小さくします。
ポリゴンを拡張するプロセスは、アプリケーションで繰り返し呼び出されます。
この問題を正しく読んでいれば、それは不可能です。曲線に沿った N 個の点で定義され、直線エッジには何もない「半円」を考えてみましょう。P1 と P2 を 2 つの半円とし、これらの直線エッジは (| |) のように向かい合っています。明らかに、それらの両方を含む唯一の多角形は、すべての 2N ポイントで構成されています。
単純な問題 (新しい頂点を導入し、削除する古い頂点を選択する) も不可能です: 三角形と、エッジの中央近くにある新しい点を考えてみましょう。
内部が失われてはならないという要件を放棄すれば、問題は解決できますが、完全には解決できません。これらのいくつかを試して、どのスイートが最適かを確認することをお勧めします.
許容できるポイント密度を持つ一連のポリゴンを見つけようとしているようです。一連の凸包を構築することを検討しましたか? ポイントを追加するたびに新しい凸包を構築して、セットを外側に拡張します。新しい船体の密度を見つけます。受け入れられない場合は、ポイントを削除して別のポイントを選択します。目標エリアまたは総ポイント数に達したら停止します。
これは逆に適用することもできます。最初のポリゴン P1 と P2 を使用して凸包をシードし、単一のポイントを破棄して新しい密度を計算することを検討できます。削除する最も有用なポイントは、密度の増加を最大化するポイントです。満足するまで繰り返します。