Javascript扫描线算法查找具有相同x坐标的所有元素

Question

我试图通过使用PURE Javascript(没有其他框架)来实现线扫描算法,它基本上从左到右扫描屏幕并查看共享相同x坐标的所有元素(包括重叠元素).

例如

我有6个div带黑色边框的元素,它们都在屏幕上随机排列.为了便于说明,我使用垂直虚线蓝线从左到右扫过飞机.目标是报告该行传递的所有元素.对于上面的例子,我们如何报告Div A,Div E,Div D,也是hyperlink D内Div D通过使用JavaScript？

Answer 1

getBoundingClientRect您可以使用方法获取元素的位置。然后循环它们并检查它们是否与您的扫描匹配：

var all = document.body.getElementsByTagName("*");
var x = /* blue line */;
var match = [];
for (var i=0; i<all.length; i++) {
    var rect = all[i].getBoundingClientRect();
    if (rect.left < x && rect.right > x)
        match.push(all[i]);
});

更短、更实用的方式：

var match = Array.prototype.filter.call(document.body.querySelectorAll("*"), function(el) {
    var rect = el.getBoundingClientRect();
    return rect.left < x && rect.right > x;
});

如果您需要经常使用的快速访问功能，您可以将所有元素（及其坐标）存储在排序的数据结构（线段树）中，您可以在其中搜索它们。

另外，当保证 DOM 元素的子节点不超出其父节点边界时，您可以轻松地将 DOM 本身用作搜索树：

var x = /* the blue line */;
var match = function find(el, set) {
    var rect = el.getBoundingClientRect();
    if (rect.left < x && rect.right > x) {
        set.push(el);
        for (var i=0; i<el.children.length; i++)
            find(el.children[i]);
    }
    return set;
}(document.body, []);