Webサービスを介して100万ポリゴンの数千のポイントを見つけようとしました.最初はJavaでアルゴリズム(ポリゴンのポイント)を実装しましたが、長い時間がかかりました.そして、mysqlでテーブルを分割し、複数を使用しようとしましたそれを解決するためのスレッドですが、それでも非効率的です。これを解決するためのより高速なアルゴリズムまたは実装はありますか?
ポリゴンについての説明を追加。2D、静的、複雑なポリゴン (穴もあり)。
任意の提案をいただければ幸いです。
質問する
1673 次
4 に答える
3
ポリゴンのコレクションが静的である場合は、最初にそれらを空間データ構造に登録することが役立つ場合があります。ポリゴンが互いにあまりオーバーラップしないと仮定すると、 R ツリーが適切な選択になる可能性があります。
ポリゴン コレクションに対してポイントをテストするには、ツリー内の囲んでいるリーフが最初に検出され (O(log(n))スタイル操作)、次に、囲んでいるリーフに関連付けられているポリゴンに対してポリゴン内の完全なポイント テストを実行するだけで済みます。 .
このアプローチにより、各ポイント テストが大幅に高速化されますが、R ツリーを構築するための追加のセットアップ フェーズが必要になります。
お役に立てれば。
于 2012-04-27T06:57:27.897 に答える
3
ポイント イン ポリゴン関数がどれほど効率的であっても、100 万個のポリゴンに対してポイントをテストするには、多くの時間がかかります。
検索リストを絞り込む必要があります。各ポリゴンのバウンディング ボックスを作成し、ポイントがバウンディング ボックス内にある場合にのみポリゴンを選択することから始めます。
ポリゴンが変更されていない場合は、各ポリゴンを一連の三角形に変換できます。ポイントが三角形にあるかどうかを確認するテストは、任意の多角形にあるかどうかを確認するテストよりもはるかに高速です。三角形の数はポリゴンの数よりもはるかに多くなりますが、全体的には高速になる可能性があります。
于 2012-04-27T04:37:56.030 に答える
1
数百万のポリゴンを扱う場合、何らかの空間分割が必要です。そうしないと、ヒット テスト関数がどれほど最適化されていても、クエリを解決するためにいくつのスレッドが動作していても遅くなります。
どのような空間分割ですか? それは依存します：
- 二次元？3D?
- ポリゴン セットは静的ですか? そうでない場合、頻繁に変更されますか?
- このセットではどのようなリクエストを行っていますか?
- どんなポリゴンですか？三角形？凸？凹んだ？複雑？穴あり？
お役に立てる情報がさらに必要です。
編集
これは単純なスペース分割スキームです。
与えられたステップで 2D 空間上にデカルト グリッドがあるとします。
ポリゴンを追加する場合:
- その境界ボックスを計算します
- 境界ボックスと交差するすべてのグリッド セルを見つける
- セルごとに、特別なテーブルに行を追加します。
テーブルは次のようにcell_xなります。適切なインデックスを追加します (少なくともおよび)cell_ypolygon_idcell_xcell_y
もちろん、ほとんどのポリゴンが 10 個未満のセルに配置されるようにグリッド ステップを選択する必要があります。そうしないと、セル テーブルがすぐに巨大になります。
特定のポイントでポリゴンを簡単に見つけることができるようになりました。
- ポイントが属するセルを計算します
- このセルに関連付けられているすべてのポリゴンを取得します
- ポリゴンごとに、ヒットテスト関数を使用します
このソリューションは最適とは言えませんが、実装は簡単です。
于 2012-04-27T07:18:14.573 に答える
0
私はここで分割統治が行われる場合だと思います。サブポリオンを作成したり、いくつかのポントを単純化したり、ヒューリスティックなアプローチを試したりすることができます。私の 5 セントがあります。
于 2012-04-27T04:12:55.893 に答える