200の頂点（lat、lng）からなる凸ジオポリゴンがあります。それをMと呼ぶことができます。 内部にジオポイントのセットがあります（約15 000ポイント）。 P = {1 ... 15 000}。 また、最初の1つ（M）の内側にもう1つの凸ジオポリゴンがあり、50の頂点から成っています。 ポリゴンSにはP点の43％が含まれています。 Pの点の55％を含む最小領域を得るために、（元のポリゴンSの点を動かして）Sの面積を増やすアルゴリズムが必要です。 出来ますか？ジオポイントのXパーセンテージをカバーするアルゴリズムを見つけるアルゴリズム
変性S（S 'それを呼び出すことができます）ここでM.
内に例えば100％とする必要がある場合、それは常に可能ではない。
レッツMがどこ43％円の一種でありますの点の中心は、円の周縁上の57％の他の点の近くにあります。 Sを三角形にして、円の辺の角を持つようにします。
円内の点の最大3つだけがMの中にあるので、三角形内の円の縁に点の数を増やす方法はありません三角形。だから三角形のままで、コーナーがMの中に入っていなければならない限り、S 'の55％を達成することはできません。
いいえ、S 'はM内で100％である必要はありません。この場合、ポリゴンの交差を適用するだけです。 –
しかし、実際に重要なことは、点が不均等に分布しているため、S 'ポリゴンが面積で最小になることです。 –
Sにエッジを追加するのはどうですか？ Sは本当にSと同じ量のコーナーを持つ必要がありますか？ – MrSmith42
少なくとも新しいSがまだ完全には必要ない場合M以内）。問題はどのアルゴリズムの複雑さですか？ – MrSmith42
アルゴリズムの複雑さは重要ではありません。なぜなら、アルゴリズムは1回だけ計算され、次に静的なデータを取るためです。しかし、重要なことは、結果のS 'ポリゴンのタイプです。凸でなければなりません。 –