什么是在一定距离内找到所有点的有效方法？ （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) { 

---

早期消除点的另一种方法是将屏幕划分为最大距离一侧的正方形，并将点存储在每个正方形的单独数组中（或将正方形数字附加到每个点）。在查看某个点时，您知道最大距离内的点只能位于同一个正方形或八个周围正方形中的任何一个。

这当然意味着当你移动点时需要做更多的工作，因为你必须检查一个点属于哪个数组，但是随着点的数量线性增长，而距离计算随着点的数量呈指数增长点。