Javascript sweep line algorithm finding all elements with the same x coordinate

Question

I am trying to implement line sweep algorithm by using PURE Javascript (no other frameworks) that basically scans through the screen from left to right and looks all the elements (including overlapped elements) that share the same x coordinate.

For example

I have 6 div elements with black border, and they all layout randomly on the screen. for illustration purposes I am using a vertical dotted blue line to scan through across the plane from left to right. The goal is that report all the elements that the line passed over . For the example above, how do we report that Div A, Div E, Div D and also the hyperlink D within Div D by using JavaScript ?

Answer 1

You can get the position of elements with the getBoundingClientRect method. Then loop over them and check whether they match your scanning:

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]);
});

Shorter, functional way:

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

If you need a quick-access function for often use, you would store all elements (with their coordinates) in a sorted data structure, a segment tree, where you can search for them.

Also, when it is guaranteed that child nodes of DOM elements do not exceed their parents boundaries, you can easily use the DOM itself as a search tree:

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