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

algorithm, javascript

Solution

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

Problem

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 ?

Original source