2016-08-04 13 views
0

2次元平面上の座標を表す大きなデータセットがあります。可変点を中心に可変半径内にあるすべてのx、yペアを見つけるには、効果的かつ効率的な方法は何でしょうか?特に特定の領域に入る2次元データ点を見つける

最終的なアプリケーションはJavascriptで書かれている

EDIT、ノード(それが簡単に処理するだろうデータを格納するための任意のヒントも大歓迎です)。 Iは、矩形領域ではなく半径よりも許容可能であることがわかりました

EDIT、矩形の境界はまだしかし、可変であろう。私は以下のコメントで述べましたが、最終データセットには何百万ものエントリがあり、各要求ごとにセット全体を実行することは実現不可能であることを指定する必要があります。

+0

あなたは手前で検索することを知っていますか?空間クエリをサポートするデータベースを使用できますか? –

+0

各クエリーの半径は常に同じサイズになりますか?それはどれくらい違うのですか?これは、あなたの目的にとって最も効率的な空間データ構造の選択に影響します。 – samgak

+0

これは現在のデータの生のテーブルです。私はそれを保存するための提案を受けていますが、ローカルに保存し、Node.jsアプリケーションからアクセス可能である必要があります。探索されるポイントは様々ですが、毎回知ることは明らかです。半径も可変です。 – FatalKeystroke

答えて

1

ポイントツーポイント距離は、検索対象のサークルの半径より小さくする必要があります。検索を改善するために、バイナリ検索またはkd-treeを実装することもできます。

var getPoints = (function() { 
 
    var points = [{ 
 
    x: 90, 
 
    y: 70 
 
    }, { 
 
    x: 100, 
 
    y: 80 
 
    }, { 
 
    x: 20, 
 
    y: 40 
 
    }] 
 
    return function() { 
 
    return points; 
 
    } 
 
})(); 
 

 
function dist(point1, point2) { 
 
    var pow = Math.pow; 
 
    return Math.sqrt(pow((point2.x - point1.x), 2) + pow((point2.y - point1.y), 2)); 
 
} 
 

 
function drawCircle(centerX, centerY, radius, fill) { 
 
    var canvas = document.getElementById('myCanvas'); 
 
    var context = canvas.getContext('2d'); 
 

 
    context.beginPath(); 
 
    context.arc(centerX, centerY, radius, 0, 2 * Math.PI, false); 
 
    if (fill) { 
 
    context.fillStyle = 'green'; 
 
    context.fill(); 
 
    } 
 
    context.lineWidth = 2; 
 
    context.strokeStyle = '#003300'; 
 
    context.stroke(); 
 
} 
 

 
function spatialSearch(centerX, centerY, radius) { 
 
    var points = getPoints(), 
 
    res = [], 
 
    len, 
 
    r = 5, 
 
    fill, 
 
    i; 
 

 
    drawCircle(centerX, centerY, radius); 
 

 
    for (i = 0, len = points.length; i < len; i += 1) { 
 
    ele = points[i]; 
 
    fill = undefined; 
 
    if (dist({ 
 
     x: centerX, 
 
     y: centerY 
 
    }, ele) <= radius) { 
 
     res.push(ele); 
 
     fill = 'green'; 
 
    } 
 
    drawCircle(ele.x, ele.y, r, fill); 
 
    } 
 
    return res; 
 
} 
 

 
spatialSearch(100, 75, 50);
<canvas id="myCanvas" width="300" height="150" style="border:1px solid #d3d3d3;"> 
 
    Your browser does not support the HTML5 canvas tag.</canvas>

+0

データセットのサイズのため、クエリごとにセット全体をトラバースすることは問題になる可能性があります。これは100%ではなく、99.999%です。最終的なデータセットは数百万のポイントを持ち、一度に複数のクエリを満たすことができる必要があるため、各ポイントを評価することは多すぎる可能性があります。 – FatalKeystroke

0

アヤンのアプローチ@非常にstraighforwardであるが、ここで考慮すべきいくつかの他の技術です。実際のデータが何であるかを知るためには、実際のデータを測定する必要があります。

ポイント数が非常に多い場合、ステップ1は、サークルを含む境界ボックスの外にあるすべてのポイントを取り除くことです。円が半径rの(ox、oy)の中心にあるとしましょう。次に、x値がox +/- rの外にある(y値についても同じ)すべてのポイントを破棄することができます。あなたのポイントがx座標でソートされている場合は、バイナリ検索を使用してx座標を絞り込み、残ったポイント候補に対して可能性のあるy値で線形スキャンを実行できます。

次に、最も簡単なアプローチは、真理値距離の2乗をr^2と比較することです。これは、@Ayanが上で行っている標準距離公式で平方根を行うことを避けますが、これはかなり高価です。だから、r^2が(ox - px)^ 2 +(oy - py)^ 2より小さいかどうかを計算するだけです。後者は単に加算と乗算であるため、合理的に速くすべきです。

近似を受け入れることができる場合は、サークル上の特定のバケットに沿って円の-yと+ yをサンプリングし、ルックアップテーブルに格納することを検討してください。次に、与えられた点(x、y)に対して、そのxの適切なバケットを探し、yが事前計算した点の間にあるかどうかを確認します。あなたは本当にこれが速くなるために多くのポイントを持っている必要があります。

+0

ポイントをxでソートし、そこから絞り込むことができます。それは非常に大きなポイントですので、私はそれを試して、パフォーマンスにあまり影響を与えることなく実装できるかどうかを見ていきます。私はそれがうまくいくかどうかはわかりませんが、私は何百万という点でそれを扱うことができなければなりません。 – FatalKeystroke

+0

@Ayanが提案したように、k-dツリーを使用するかもしれません。この構造は、このような効率的な範囲検索を行うことを意味しています。少なくとも3つのノードパッケージが実装されています。他の2つのベンチマークがあるhttps://github.com/mikolalysenko/static-kdtreeを参照してください。 –

関連する問題