長方形内に含まれる一連のポイントがあります。ポイント密度に基づいて長方形をサブ長方形に分割したいと思います（サブ長方形の数または目的の密度のいずれか簡単な方を指定します）。
分割は正確である必要はありませんが（通常のグリッドよりも優れた近似はほとんどありません）、アルゴリズムは多数のポイントに対処する必要があります。2億。ただし、必要なサブ長方形の数は大幅に少なくなります（約1000）。
この特定のタスクで私を助けるかもしれないアルゴリズムを誰かが知っていますか？
5059 次
8 に答える
2
あなたは標準的なKdツリーまたはバイナリ空間分割ツリーを求めていると思います。（ウィキペディアで調べることができます。）
あなたは非常に多くのポイントを持っているので、最初のいくつかのレベルをおおよそ分割したいと思うかもしれません。この場合、200Mポイント（おそらく200kポイント）のランダムサンプルを取得し、サブサンプルの中間点で（どちらか長い方の軸に沿って）完全なデータセットを分割する必要があります。実際にランダムにポイントを選択した場合、細分化する必要のあるポイントの巨大なクラスターを見逃す可能性はほぼゼロになります。
今、あなたはそれぞれ約1億ポイントの2つの問題を抱えています。それぞれを長軸に沿って分割します。サブサンプルの取得を停止し、データセット全体に沿って分割するまで繰り返します。幅優先探索を10回繰り返すと、完了です。
別の問題がある場合（Kdツリーを不規則に分解するのではなく、X軸とY軸に沿って目盛りを付け、それらに沿ってグリッドをできるだけ埋める必要があります）、ポイントのサブサンプルを取得し、各軸に沿って0/32、1 / 32、...、32/32パーセンタイルを見つけます。そこにグリッド線を描画し、結果の1024要素のグリッドをポイントで塗りつぶします。
于 2010-06-02T18:40:48.853 に答える
2
于 2010-06-02T16:32:42.633 に答える
2
問題を理解するためだけに。以下は粗雑でパフォーマンスが悪いですが、結果があなたが望むものであるかどうか知りたいです>
仮定>長方形の数は偶数です
仮定>点の分布は著しく2Dです（1行に大きな蓄積はありません）
手順>
いずれかの軸でn/2回二等分し、「通過した」ポイントをカウントし、各反復で通過したポイントの数を格納する、以前に決定された各長方形の一方の端からもう一方の端にループします。カウントしたら、各ループでカウントされたポイントで選択する長方形を二等分します。
それはあなたが達成したいことですか？
于 2010-06-02T16:41:51.940 に答える
2
私は、@belisariusがすでに提案したものに近い以下から始めると思います。「長くて細い」長方形よりも「ほぼ正方形」の長方形を優先するなど、追加の要件がある場合は、この単純なアプローチを変更する必要があります。簡単にするために、ポイントはほぼランダムに分布していると仮定します。
- 最初の長方形を、長方形の短辺に平行で中点を正確に通る線で2つに分割します。
- 両方の半長方形の点の数を数えます。それらが等しい（十分）場合は、ステップ4に進みます。それ以外の場合は、ステップ3に進みます。
- 半長方形間の点の分布に基づいて、線をさらに上に移動します。したがって、パーチャンスで、最初のカットがポイントを1 / 3、2 / 3に分割した場合、線を長方形の重い半分に半分移動します。手順2に進みます（ここに閉じ込められないように注意してください。最初に一方の方向に、次にもう一方の方向に、徐々に減少するステップでラインを移動します。）
- ここで、ステップ1で、各半長方形をこの関数の再帰呼び出しに渡します。
それが提案の概要を十分に示していることを願っています。制限があります。2の累乗に等しい数の長方形が生成されるため、それが十分でない場合は調整してください。再帰的に表現しましたが、並列化には理想的です。各分割により2つのタスクが作成され、それぞれが長方形を分割してさらに2つのタスクを作成します。
そのアプローチが気に入らない場合は、必要な長方形の数の倍数（おそらく10〜100）の通常のグリッドから始めることができます。これらの小さな長方形のそれぞれの点の数を数えます。次に、小さい長方形に（ほぼ）適切な数のポイントが含まれるまで、小さい長方形の接着を開始します。または、要件を十分に満たす場合は、これを離散化方法として使用し、最初のアプローチと統合できますが、切断線は小さな長方形の境界に沿ってのみ配置します。小さな長方形ごとにポイントを1回カウントするだけでよいので、これはおそらくはるかに高速です。
私はこれらのどちらの実行時間についても実際には考えていません。私は前者のアプローチを好みます。私はかなりの量の並列プログラミングを行い、プロセッサをたくさん持っています。
于 2010-06-02T17:07:28.547 に答える
0
K-meansクラスタリングまたはボロノイ図は、解決しようとしている問題に適していますか？
于 2010-06-02T18:40:45.500 に答える
0
QuadTreeは機能しますか？
クワッドツリーは、各内部ノードに正確に4つの子があるツリーデータ構造です。四分木は、2次元空間を再帰的に4つの象限または領域に分割することにより、2次元空間を分割するために最もよく使用されます。領域は、正方形または長方形である場合もあれば、任意の形状を有する場合もある。このデータ構造は、1974年にRaphaelFinkelとJLBentleyによってクワッドツリーと名付けられました。同様のパーティショニングはQツリーとも呼ばれます。すべての形式のQuadtreeは、いくつかの共通の機能を共有しています。
- それらは空間を適応可能な細胞に分解します
- 各セル（またはバケット）には最大容量があります。最大容量に達すると、バケットが分割されます
- ツリーディレクトリは、Quadtreeの空間分解に従います
于 2010-06-02T19:34:04.860 に答える
0
良い質問。
調査する必要のある領域は、「計算幾何学」と「k-partitioning」の問題だと思います。ここから始めるのに役立つリンクがあります
問題自体がNP困難であることに気付くかもしれません。これは、適切な近似アルゴリズムが得られる最良のアルゴリズムであることを意味します。
于 2010-06-02T18:36:31.980 に答える
0
これは、クラスター分析のように見えます。
于 2010-06-02T18:44:41.030 に答える