0

N個の（x、y）点がK個の長方形の内側にあるかどうかを確認する効率的な方法はありますか？現在、ブルートフォースアプローチを実行してすべてのポイントと長方形をループしていますが、200,000ポイントと44の長方形で約2分30秒かかります。

私はGoogleマップを使用して、ポイントがマップ上のルートに近いかどうかを確認するプログラムを作成しています。パスに沿って複数の長方形と円を計算し、既存の点がこれらの長方形と円の中にあるかどうかをテストします。

1.ルートの性質によっては、長方形が重なる場合があります。
2.ポイントは長方形の1つにある必要があります
3.ポイントが長方形の端にある場合は、長方形の内側としてカウントしたいと思います（ただし、カウントしない方が簡単な場合はカウントしませんit）
4.長方形は、ルート外で検索したいエリアによって異なります。通常、高さは2マイル（ポイントから各方向に1マイル）、ポイント1からポイント2までの距離は幅です。

4

2 に答える 2

1

考えられるアイデアは次のとおりです。

  • あいまい一致-ポイントを特定の長方形内にあるものとして100％正確にマークする必要がない場合は、より効率的な「最良の推測」を行うアルゴリズムを作成できますが、犠牲は100％正確です。
  • 最初にファジー、後で正確-与えられた点と長方形の左上隅、または円の中心との間の距離を計算するだけで、おおよその答えをすばやく与えることができます。これにより、100％正確ではない可能性のあるおおよその答えが得られますが、計算を非同期的に続行して調整し、しばらくしてから100％正確なデータで表示を更新することができます。
  • ポイントをグループ化します-ポイントが作成されたら、それ自体を長方形に「登録」します。基本的に、可能であれば、ポイントが特定の長方形内にあるかどうかを事前に計算します。
  • Pre-calculate + cache-次に、特定のポイントが収まる長方形のリストをポイント自体にキャッシュします。そうすれば、毎回再計算するのではなく、単純なルックアップになります。
  • 非同期読み込み-計算中に回答の表示を開始できますか？バッチ全体を実行するのに2.5分かかる場合、計算時に結果を1,000ポイントのチャンクで表示できますか？このようにして、計算が作業を終了している間、ユーザーはすぐにフィードバックを受け取り始めます。2.5分で、それは150秒です。1,000ポイントのチャンク（一度にデータの約1/200）で結果を配信できる場合は、ポイントマップが利用可能になったときに、毎秒1回更新できる可能性があります。
于 2011-06-10T14:37:55.713 に答える
1

理論的には、最高の状態で200,000ポイントすべてを反復処理する必要があります。最悪の場合、44個の長方形すべてに対してこれらのポイントすべてをチェックする必要があります（これが現在実行していることです）。

200,000ポイントすべてをループする必要があることがわかっているので、44個の長方形すべてをチェックする必要がないようにするのが最善の方法です。

これを行うには、長方形に対していくつかの計算を行う必要があります。最も近い2つの長方形を見つけて、両方を囲む大きな長方形を形成します（必要に応じてクラスター）。次に、形成したばかりの長方形に次に近い長方形を見つけて、別のクラスター長方形を形成します。すべての長方形を囲むまでこれを続けます（43個のクラスター長方形ができあがります）。

次に、ポイントをループして最大の長方形をチェックします。ポイントがその長方形内にある場合は、次に大きい長方形をチェックします。その長方形内にない場合は、をチェックするだけで、その範囲内にあるかどうかを確認できます。その長方形を形成するために使用された長方形。その長方形に含まれない場合は、次のポイントに移動できます。これは、そのポイントがどの長方形にも含まれないためです（3回のチェックでこれを発見しました）。

于 2011-06-10T15:09:43.730 に答える