c++ - 格子を円で切り取る - 格子点 求め方 円




与えられた半径の1つの円で最大点数をカバーするアルゴリズム (7)

O(n)近似アルゴリズムとO(n ^ 2 log n)正確(非近似)アルゴリズムの2つのアイデアがあります:

高速近似

ローカリティセンシティブハッシングを使用する。 基本的に、各ポイントをすべての近くのポイントを含むハッシュバケットにハッシュします。 バケットは、近くのポイント間でのみ衝突が発生するように設定されています。類似の名前のハッシュテーブルとは異なり、ここでは衝突が便利です。 バケット内の衝突数を連続してカウントし、そのバケットの中心をサークルの中心として使用します。

私は、これが最初にあなたがそれを聞いたときには、はっきりとした概念ではないことを素早く説明していることを認めます。 類推は、郵便番号が何であるかを人々に尋ね、最も一般的な郵便番号を使用して最も人口の多いサークルを決定することです。 それは完璧ではありませんが、良いヒューリスティックです。

基本的にはポイント数のリニアな時間で、データセットを即座に更新して、ポイントごとに一定の時間内に新しい回答を徐々に得ることができます(n =ポイント数で一定です)。

ローカリティに敏感なハッシュについての一般的な情報、この場合に動作する個人的に好きなバージョンについての情報。

ブルートフォースよりも優れた決定論的アプローチ

アイデアは:各点について、その点に円の端を置き、どの方向に最も多くの点が含まれているかを見るために円を掃引します。 すべての点でこれを行い、グローバル最大値を見つける。

点p周りの掃引は、n log n時間で行うことができます。(a)角度θで円を配置するときに、qを含むように他の点qごとの角度間隔を求めます。 (b)線形時間でpの周りを行進/掃引できるように間隔をソートする。

だから、O(n log n)時間で固定小数点pに触れる最善の円を見つけて、O(n)でそれを掛けてすべての点をチェックします。 合計時間はO(n ^ 2 log n)です。

いくつかの点がある平面があるとしましょう。 与えられた半径の円もあります。

最大の可能なポイント数をカバーする円の位置を決定するアルゴリズムが必要です。 もちろん、そのような位置が多数あるため、アルゴリズムはそれらの位置の1つを返す必要があります。
精度は重要ではなく、アルゴリズムは小さなミスをする可能性があります。

ここでは例の写真です:

入力:
int n (n <= 50) - ポイント数。
float x[n]float y[n] - ポイントのX座標とY座標を持つ配列。
float r - 円の半径。

出力:
float cxfloat cy - 円の中心の座標

アルゴリズムのライトニング速度は必要ありませんが、遅すぎるようにしてはいけません。

C ++コードが推奨されますが、必須ではありません。


あなたは全体の領域をピクセル化し、各点に移動し、その点を中心とした半径の円内のすべてのピクセルの値を増やすことができます。 最高の合計を有する画素は良好な候補である。

もちろん、丸め誤差のために良い領域や「幻覚」の良い領域を失う可能性があります。 おそらく、あなたはまず粗いピクセル化を行い、次に有望な領域を洗練することができます。


これは文献の「ディスクの一部をカバーする問題」です。グーグルグレーディングを開始するのに適しています。 1つの可能な解を扱う論文がありますが、数学的には少し激しいです: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf : http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

実際には、これは計算幾何学と呼ばれる領域にあります。これは魅力的ですが、トーンホールドを得るのが難しい場合があります。テーマに関連するさまざまなアルゴリズムについてdeBergが概説しています。



単純なものを望むならば、ランダムな位置(x、y)をとり、円の中の点の数を計算し、前の位置と比較してください。 最大限に活用してください。 必要なときにいつでも操作を繰り返します。

なぜ地獄downvote? Monte Carloメソッドについて聞いたことがありますか? 実際には膨大な量の点について、決定論的アルゴリズムは妥当な時間に終了しないことがあります。


密度マップをお勧めしますか? xとyの最小値と最大値の境界を求めます。 xとyの範囲の範囲を、サークルの直径に等しい幅を持つビンに分割します。 xとyの各ビン内の点の数を別々に数えます。 最も高いランクのxビンと最も高いランクのビンとの密度マップ上の交差点を見つけてください。

これは、大量のデータセットをすばやく一般化するための非常に高速なアルゴリズムですが、正確性を向上させるために、ビンを小さく小さくしたり、ビンの位置を左右にn回シフトしたり、投票システムを使用して試行の間に最も頻繁に発生する回答を選択します。


精度が重要でなく、アルゴリズムが小さなミスをしているのであれば、私は次のように思います。

点(0,0)に最大値を持ち、半径Rの円の内側の点でのみ有意である関数であるとするf(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}

(x_i,y_i)を点とし、 E_i(x,y) = f(x - x_i, y - y_i)

あなたの問題は、 \sum_i E_i(x,y)最大値を見つけることです。 。

各点から勾配降下を開始することができます。





points