我想知道最好的解决方案是什么。单击鼠标时返回并显示网页上最近的超链接。
本例中有 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 是我们拥有的链接数。我们可以做得更好吗?
最佳答案
这看起来像一个最近的邻居
问题,例如您有一组二维的 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)
几乎所有的方法都是相同的。
关于单击鼠标时,Javascript获取网页上最近的超链接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12230456/