特定の領域に入る2次元データ点を見つける

Question

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

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

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

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

Answer 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>

Answer 2

アヤンのアプローチ@非常に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が事前計算した点の間にあるかどうかを確認します。あなたは本当にこれが速くなるために多くのポイントを持っている必要があります。