与えられた領域を持つ矩形に含まれる点の最大数を求める

それぞれが.xと.y座標を持つ点b [0..n-1]の配列が与えられているとする。 nは大きくてもよい。与えられた領域を持つ矩形に含まれる点の最大数を求める

問題のための効率的なアルゴリズムを考案する：与えられた面積を持つ矩形内に含まれる点の最大数を見つける。

時間複雑度O（n^2 * k）で行いたいと思っています。ここで、kは矩形以上の最大点です。

2016-04-17 Algor7

宿題ですか？ – m69

絶対にそうではありません...プロジェクトにとって私の必要条件です。 – Algor7

@ Algor7プロジェクトの内容についていくつかの文脈を与える必要があります。たとえば、ポイントの集合を関数で記述できる場合など、最適化について多くのことが分かります。 – ChatterOne

頂点が三角形の場合、これは非常に簡単です。配列bのすべての点についてクロス積を解くことができます。

Cross1 = [AO, AB], Cross2 = [BO, BC], Cross3 = [CO, CA]を計算することができます。

たとえば、Cross1 = AO.x * AB.y - AO.y * AB.x。

各変数Cross1, Cross2, Cross3は同じ記号でなければなりません。

ポイントごとにこれをチェックし、ポイントを矩形にカウントします。次に、kN = O(N)があります。

2016-04-19 00:00:16 hedgehogues

私はこれが質問に答えるとは思わない。問題は、どの点が指定された図形の中にあるかをチェックすることではなく、図形を選択してその中の点の数を最適化することです。（質問が多少曖昧な場合は、回答に努力する前に、最初に明確にすることをお勧めします）。 – m69

長方形は軸合わせされていなければならないと申し訳ありません。 – Algor7

ご迷惑をおかけして申し訳ありません。 Rectangleは指定されていない領域だけが与えられ、同じ領域のすべての可能な矩形を見つけ、その中に最大点を持つ矩形を見つけなければなりません。私たちは長方形には関心がなく、最大点数に興味があります。 – Algor7

答えて