单击鼠标时，Javascript获取网页上最近的超链接

Question

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

本例中有 3 个 DIV。他们每个人都在里面带有一个超链接。还有另一个超链接(超链接 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 是我们拥有的链接数。我们可以做得更好吗？

Answer 1

这看起来像一个最近的邻居问题，例如您有一组二维的 n 个点和一个查询点 q。 S中的哪一点最接近q。

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

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

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

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

几乎所有的方法都是相同的。