頂点として選択された場合、ポリゴンの面積を最大化する点を決定する

Question

頂点が他の4つのポリゴンの中心点であるポリゴンを持っています。これらの4つのポリゴンには、頂点の座標もあります。私は、より大きなポリゴンの頂点として選択された場合、その頂点を最大にする頂点を各コーナーポリゴンについて決定したいと考えています。ポリゴンは、透視変換が適用された矩形ですので、台形だと思っていました。

私は、この中心点から最も遠い距離を有していた一方に基づいて、各頂点を選択した4により（X、Y）の角部とダイビングを合計することによって粗中心を計算しようとしていますそれは仲間の間です。 （distance = (Xc - X)^2 + (Yc - Y)^2のようなものですが、パフォーマンスのために結果を平方根にすることは避けました）。

これは残念ながら、意図した結果を出すものではありません。通常、ただ一つの頂点は、最も外側の "コーナーポリゴン"頂点に置き換えられ、他の頂点は、最も近いものを除く他の2つのコーナーポリゴン頂点のうちの1つによって置換される。

より良いアルゴリズムを作成する方法は何ですか？

Answer 1

最初のアプローチは、ブルートフォースだけです。組み合わせによって得られた4^4 = 256ポリゴンの面積を比較します。

ちょっと良い点は、頂点が点集合の凸包に属している必要があると思います（確認する必要があります）。その後、内側の点を破棄し、残りの点をブルートフォースします。コーナー四角形の1つと3つの頂点の間が凸包上にあるので、最悪の場合は3^4 = 81の組み合わせがあります（そして最高でも1つです;この例では4つ、実際には2^4 = 16が最も可能性があります）。

あなたは貯蓄を有効にするには、効率的な凸包アルゴリズムが必要になります。

Answer 2

実際に投稿した方法は、@MBoが実装ミスを示唆しているため、実際には動作します。将来の読者に指定するには、ポリゴンが凸型および/または台形であるため、このアルゴリズムはおそらく機能しますが、それは私のアルゴリズムがヒューリスティックに生成されたという事実に基づく純粋な推測のままです。