什麼是在一定距離內找到所有點的有效方法？ （Javascript）

Question

我的靈感來自Jennifer Dewalt的項目169：Electro Bounce（鏈接：http://jenniferdewalt.com/electro_bounce/page）我想從一個粗略的想法開始，並將其添加到我的初始頁面。我看到在她的頁面中，線條是在彼此相距一定距離內的任何節點之間繪製的。什麼是有效的方式來實現這個（在Javascript中）？任何建議或提示表示讚賞，謝謝

Answer 1

要找到一定距離內的所有點，你必須比較每個點與所有其他點。然而，有些事情可以儘早消除點，而無需比較它們之間的確切距離。

當看一個點時，想象一下用最大距離的半徑繪製一個圓。要連接的點將位於此圈內。

現在想象一個正好包含圓的正方形。要考慮的要點將在sqare內，再加上角落裏的幾個點。檢查一個點是否與一個圓形相比要容易得多，所以當你單擊了正方形中的點時，可以檢查它們是否在圓內。

因此，通過計算平方的範圍開始（x和y是您lookning周圍穴位，並d是最大距離）：

var x1 = x - d, y1 = y - d, x2 = x + d, y2 = y + d; 

通過積分循環，你可以檢查是否有點（px和py）是正方形內：

if (px >= x1 && px <= x2 && py >= y1 && py <= y2) { 

然後你可以檢查它是否是圈內。您可以使用Pythagoras theorem來計算點之間的距離。距離是垂直和水平距離之和的平方根，而平方根是一個昂貴的計算，所以不是你應該得到的總和，並將它與距離的平方：

if ((px - x) * (px - x) + (py - y) * (py - y) <= d * d) { 

---

早期消除點的另一種方法是將屏幕劃分爲最大距離一側的正方形，並將點存儲在每個正方形的單獨數組中（或將正方形數字附加到每個點）。在查看某個點時，您知道最大距離內的點只能位於同一個正方形或八個周圍正方形中的任何一個。

這當然意味着當你移動點時需要做更多的工作，因爲你必須檢查一個點屬於哪個數組，但是隨着點的數量線性增長，而距離計算隨着點的數量呈指數增長點。