查找屬於特定區域的2d個數據點

我有一大組數據表示二維平面上的座標。找到所有基於變量點的變量半徑內的所有x，y對都是一種有效且高效的方法？（用於存儲，將使加工更容易的數據有什麼建議也非常歡迎）查找屬於特定區域的2d個數據點

編輯

最終應用正在Javascript編寫的，具體的節點。

編輯

我發現一個矩形區域也是允許的，而不是一個半徑，矩形的邊框仍然是可變的但是。我在下面的評論中指出，我應該指定最終的數據集將有數百萬條目，並且遍歷整個集合對於每個請求都是不可行的。

來源

2016-08-04 FatalKeystroke

你知道要事先查找的地方嗎？您是否允許使用支持空間查詢的數據庫？ –

每個查詢的半徑總是相同的大小？如果沒有多少變化？這將影響對您的目的最有效的空間數據結構的選擇。 – samgak

這只是當前數據的原始表格。我對存儲它的建議持開放態度，但它確實需要存儲在本地並可通過Node.js應用程序訪問。搜索周圍的點會有所不同，但每次都會顯而易見。半徑也是可變的。 – FatalKeystroke

點到點的距離應小於要搜索的圓的半徑。爲了改進搜索，也可以執行二分搜索或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>

來源

2016-08-04 02:21:57 Ayan

由於數據集的大小，遍歷每個查詢的整個集合可能是一個問題。這不是100％的選擇，只有99.999％。最終的數據集將有數百萬個點，並且需要能夠同時滿足多個查詢，因此評估每個點可能太多。 – FatalKeystroke

@阿燕的做法很簡單明瞭，但這裏有一些其他技術來考慮。儘管如此，你將不得不用實際的數據來衡量真正的工作。

如果您有非常多的點數，第一步是擺脫包含您的圓的邊界框之外的所有點。假設圓圈以（ox，oy）爲中心，半徑爲r。然後你可以丟棄所有x值在ox +/- r之外的點（對於y值也是一樣的）。如果你的點是按x座標排序的，你應該能夠使用二進制搜索在x座標上縮小它，然後用一個合理的y值對剩餘的候選點進行線性掃描。

然後，最直接的方法是比較歐幾里得距離的平方與r^2。這避免了@Ayan在上面做的標準距離公式中的平方根，這非常昂貴。因此，只需計算r^2是否小於（ox-px）^ 2 +（oy - py）^ 2。由於後者只是加法和乘法，因此應該相當快。

如果您可以接受一些近似值，您可以考慮沿着圓上的特定桶對圓的-y和+ y進行採樣，並將其存儲在查找表中。然後，對於給定的點（x，y），查找該x的適當桶並查看y是否在預先計算的點之間。儘管如此，你真的必須得很多分。

來源

2016-08-04 02:39:24

保持按x排序並從此處縮小的點數可能有一個選項。這是一個非常大的一組要點，所以我會嘗試一下，看看我能否實施它，而不會對性能產生太大影響。我不確定它是否能奏效，我有數百萬分必須能夠處理。 – FatalKeystroke

你可能像@Ayan所建議的那樣使用k-d樹。這種結構意味着像這樣進行有效的範圍搜索。至少有三個節點包爲您執行。請參閱https://github.com/mikolalysenko/static-kdtree，其中有兩個基準。 –

查找屬於特定區域的2d個數據點

回答

相關問題