3

我想知道什么是最好的解决方案。单击鼠标时返回并显示网页上最近的超链接。

本例中有 3DIV秒。它们每个都带有一个超链接。还有另一个超链接（超链接 D）本身没有DIV. 假设红点是鼠标点击。

例如

我能想到的解决方案就是遍历所有链接

    var a_list = document.getElementsByTagName("a");

然后使用距离方程计算距离c^2 = a^2 + b^2，所以很简单

    var a_list = Array.prototype.slice.call(document.getElementsByTagName("a"))
    for( var i = 0 ; i < a_list.length; i++){
          Math.sqrt(Math.pow(mouseX - a_list[i].getBoundingClientRect().left,2) + 
                    Math.pow(mouseY - a_list[i].getBoundingClientRect().top,2))

    }

这种方法当然需要 O(N) 时间复杂度，其中 N 是我们拥有的链接数。我们能做得更好吗？

4

4 回答 4

2

不可能比 O(N) 更快地做到这一点，因为您确实需要检查每个链接。

如果您多次执行此检查，我可以想到更快的算法（例如，如果您每次鼠标移动时都突出显示最近的链接）；但那些一次性的启动成本比简单的检查更糟糕。

它是一个 O(N) 算法真的很重要吗？速度还不够快吗？

关于您的算法的一些注释：

  • 您可以消除昂贵的平方根计算 - 您可以比较“距离平方”值，它仍然会告诉您更接近的值。如果您确实需要某物的距离，请在找到最近的链接后，在最后取一次平方根
  • 您需要检查链接的哪个角离鼠标最近，不要盲目使用左角。即X方向：
    • 如果 mouseX < link.left 然后使用 (mouseX - link.left)^2
    • 如果 mouseX > link.right 然后使用 (mouseX - link.right)^2
    • 否则使用 0
    • ...对于 Y 方向也是如此。
  • 您可以先计算 delta_y^2 并将其与“迄今为止的最佳距离^2”值进行比较；如果它更大，则无需计算 delta_x^2。根据浏览器、CPU 和您的其余代码，这可能会或可能不会使其更快。
于 2012-09-01T19:26:23.540 回答
2

这看起来像一个nearest neighbor问题，比如你有一个二维的 n 个点的集合 S，以及一个查询点 q。S中的哪个点最接近q。

我认为，如果您要处理的链接不多（少于一百个链接），那么简单的方法是最好的（您刚刚拥有的方法。扫描每个链接并计算距离，然后取最小的一个），但是如果有数千或数百万个链接（几乎没有发生），那么您肯定需要缓存它以供以后查询，这肯定会加快查询时间。

  • 一种方法（您的方法）是获取所有链接，然后按 X 坐标对它们进行排序，您现在不关心 Y 坐标，然后对 X 进行二进制搜索，您最终会得到其中一个链接，但这可能不是最近的，您仍然需要按距离与上一个和下一个进行比较（现在使用Y坐标）。例如，从您的示例中，当您对 X 进行二进制搜索时，因为那个红色虚线（鼠标单击位置）的 X 坐标大于超链接 D，所以它将搜索之后的所有内容，但超链接 D 可能是最接近的，所以你需要考虑。这种方法需要 O(N log N) 进行排序，O(N) 空间和 O(log N) 进行查询。

  • 您也可以使用Kd 树。它适用于少量维度（在您的情况下它只有两个维度 x 和 y），并且它可以有效地搜索包含查询点 p 的单元格（您的鼠标单击位置）。
    构建时间 O(N log N)，空间 O(N) 和查询时间：O(n^1/2 + k)

  • 我能想到的另一种方法是构建Voronoi 图，它为最近邻查询提供了一种有效的数据结构，并且最适合二维。
    构建时间 O(N log N)，空间 O(N) 和查询时间：O(log n)

所以几乎所有的方法都是一样的。

于 2012-09-02T16:09:46.407 回答
1

如果您可以事先构建您的链接列表（即滚动时不滚动或重建），您可能想看看平铺。

例如，对于 0.5 的平铺因子，您会将链接分类为

  • 在屏幕左侧 0.25
  • 在屏幕左侧 0.5
  • 在屏幕左侧 0.25-0.75
  • 在屏幕左侧 0.5-1.0（=0.5 右侧）
  • 在屏幕左侧 0.75-1.0（=0.25 右侧）

垂直也是如此。

单击时，您只需检查那些与单击位置重叠的图块中的链接。如果您离最近的链接很远，这显然会给您“一无所获”，但这可能是您想要的。

于 2012-09-01T19:13:45.180 回答
1

所以，我猜你有那一页并为很多不同的鼠标位置进行计算？

在这种情况下，您可以在第一个设置中创建 2 个列表，分别保存a按 x 排序的 s，分别。y方向由它向左，分别。最高值。然后用你的鼠标事件的 x resp。y 坐标，您可以像这样开始在这些列表中搜索 - 解释 x 坐标：

从 s 的完整列表开始，a并将 mouse-x 与列表中间元素的左值进行比较。如果 x 较小，则重复但从开始到中间元素的列表，如果 x == 左值，则完成，如果 x 较大，则从中间到结尾重复列表。如果 x == left-value 或要搜索的列表只有 1 个或两个元素长，则这样做，在这种情况下，您取两者中较近的一个。

对 y 坐标也必须这样做（类似于平行）。

这还没有完全考虑清楚，但我很确定这样的事情，你可以避免a每次都与所有标签进行比较。

于 2012-09-01T19:18:27.530 回答