指定された領域（ウェブサービス）の2D点を最適に検索

Question

Javaで解決するにはアルゴリズムの種類が&の問題があります。私は2D点の大きなコレクションを持っています（そのうちの約100,000があるとしましょう）。私は、基準を満たす点P（xy）を得るために、探索点SP（X_sp、Y_sp）の周りの与えられた領域にあるそれらの集合を得たいと思う：

x X_sp - constValueとX_sp + constValueの間にあり、yはY_sp - constValueとY_sp + constValueの間です。

数字の関係を知るには、constValueは2,5,10のようになり、x、yは0と1000の間の範囲です。これはウェブサービスであることを意図しているので、同時に多くの異なる点を検索する可能性を考慮する必要があります。

これは固定点であり（計算などで変更されないため）、Xでソートされたオブジェクトと別のオブジェクトのリストを1つ用意することが最適であると考えました。最初にX範囲内のポイントを取得し、参照を使用して、別のリスト（Yでソート）からこのポイントのセットを取得します。次に、この選択をYで絞り込み、その結果得られた領域内の点を取得します。

私はJavaのインサイドアウトを知らないので、私はあなたに最も最適化されたアプローチをご相談したいと思います。範囲内のオブジェクトをすばやく検索できる並べ替え済みの点を格納するために使用するオブジェクトはどれですか？あるいは、私はこのタスクのカスタムアルゴリズムを実装する必要がありますか？また、データベースにポイントを格納する場合、結果を配信するのに十分な速さでSQLクエリを使用しますか？または、NoSQL DBがこれに適していますか？

私は自分のテストを行うつもりですが、私は最初の候補者を探しています。

Answer 1

私はおそらくマップへの鍵はx座標と各x座標であるTreeMap<Integer, TreeSet<Integer>>を、使用したい、あなたはy座標のリストを持っています。 floorEntryとceilingEntryを使用して、範囲内のx座標を見つけることができます。次に、それぞれTreeSet<Integer>が取得されたら、ceilingと​​を使用して適切なエントリを取得します。

もちろん、これはボックスの境界の座標（四隅）のみを与えます。しかし、TreeSetにはsubsetという値があります。これを2回使用する必要があります。あなたの範囲内にあるx座標の一覧（keySetのマップを使用してキーを取得できます）の場合は、それぞれxの座標の場合、範囲内のyの座標になります。だから、擬似コードは、ソートのこのようになります：

List<Point> result = new ArrayList<>(); 
int lowerX = points.ceilingKey(x - c); 
int upperX = points.floorKey(x + c); 
for each x coordinate in points.entrySet().subset(lowerX, upperX) 
    TreeSet<Integer> yCoordinates = points.get(x); 
    lowerY = yCoordinates.ceiling(y - c); 
    upperY = yCoordinates.ceiling(y + c); 

    for each y coordinate in yCoordinates.subset(lowerY, upperY) 
     result.add(new Point(x, y)) 

私はこれをテストしていませんので、私が見逃しているいくつかのバグか何かはおそらくあります。私に知らせて、私は答えを修正します。あなたは、リストを使用している場合、それはそれをルックアップするためにO(n)になるので、パフォーマンス上の利点を得る場所です -

floorとceiling呼び出しは、私は信じていlog(n)あります。

注：これが最も効果的かどうかわかりません。他の場所では運が増える可能性があるので、SOは一般的にそのような自由な質問の場所ではありません。