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

Question

我正在尝试通过使用PURE Javascript（没有其他框架）来实现线扫描算法，该算法基本上从左到右扫描屏幕并查看共享相同 x 坐标的所有元素（包括重叠元素）。

例如

我有 6 个div带有黑色边框的元素，它们都在屏幕上随机布局。出于说明目的，我使用一条垂直的蓝色虚线从左到右扫描整个平面。目标是报告该行通过的所有元素。对于上面的示例，我们如何使用 JavaScript 报告,和Div Ainside Div E？Div Dhyperlink DDiv D

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, []);

Answer 2

1. 收集所有 DOM 元素
2. 找到它们的位置并将它们存储在一个数组中（这样您就可以再次使用数据而无需通过 DOM）
3. 循环遍历数组并求解 x