Efficiently get an element's visible area coordinates

Question

StackOverflow is loaded with questions about how to check if an element is really visible in the viewport, but they all seek for a boolean answer. I'm interested in getting the element's actual areas that are visible.

function getVisibleAreas(e) {
    ...
    return rectangleSet;
}

Putting it more formally - the visible areas of elements is the set of (preferably non-overlapping) rectangles in CSS coordinates for which elementFromPoint(x, y) will return the element if the point (x, y) is contained in (at least) one of the rectangles in the set.

The outcome of calling this function on all DOM elements (including iframes) should be a set of non-overlapping area sets which union is the entire viewport area.

My goal is to create some kind of a viewport "dump" data structure, which can efficiently return a single element for a given point in the viewport, and vice versa - for a given element in the dump, it will return the set of visible areas. (The data structure will be passed to a remote client application, so I will not necessarily have access to the actual document when I need to query the viewport structure).

Implementation requirements:

Obviously, the implementation should consider element's hidden state, z-index, header & footer etc.

I am looking for an implementation that works in all common used browsers, especially mobile - Android's Chrome and iOS's Safari.

Preferably doesn't use external libraries.

Of course, I could be naïve and call elementFromPoint for every discrete point in the viewport, But performance is crucial since I iterate over all of the elements, and will do it quite often.

Please direct me as to how I can achieve this goal.

Disclaimer: I'm pretty noob to web programming concepts, so I might have used wrong technical terms.

Progress:

I came up with an implementation. The algorithm is pretty simple:

1. Iterate over all elements, and add their vertical / horizontal lines to a coordinates map (if the coordinate is within the viewport).
2. Call `document.elementFromPoint` for each "rectangle" center position. A rectangle is an area between two consecutive vertical and two consecutive horizontal coordinates in the map from step 1.

This produces a set of areas / rectangles, each pointing to a single element.

The problems with my implementation are:

1. It is inefficient for complicated pages (can take up to 2-4 minutes for a really big screen and gmail inbox).
2. It produces a large amount of rectangles per a single element, which makes it inefficient to stringify and send over a network, and also inconvenient to work with (I would want to end up with a set with as few rectangles as possible per element).

As much as I can tell, the elementFromPoint call is the one that takes a lot of time and causes my algorithm to be relatively useless...

Can anyone suggest a better approach?

Here is my implementation:

function AreaPortion(l, t, r, b, currentDoc) {
    if (!currentDoc) currentDoc = document;
    this._x = l;
    this._y = t;
    this._r = r;
    this._b = b;
    this._w = r - l;
    this._h = b - t;

    center = this.getCenter();
    this._elem = currentDoc.elementFromPoint(center[0], center[1]);
}

AreaPortion.prototype = {
    getName: function() {
        return "[x:" + this._x + ",y:" + this._y + ",w:" + this._w + ",h:" + this._h + "]";
    },

    getCenter: function() {
        return [this._x + (this._w / 2), this._y + (this._h / 2)];
    }
}

function getViewport() {
    var viewPortWidth;
    var viewPortHeight;

    // IE6 in standards compliant mode (i.e. with a valid doctype as the first line in the document)
    if (
            typeof document.documentElement != 'undefined' &&
            typeof document.documentElement.clientWidth != 'undefined' &&
            document.documentElement.clientWidth != 0) {
        viewPortWidth = document.documentElement.clientWidth,
        viewPortHeight = document.documentElement.clientHeight
    }

    // the more standards compliant browsers (mozilla/netscape/opera/IE7) use window.innerWidth and window.innerHeight
    else if (typeof window.innerWidth != 'undefined') {
        viewPortWidth = window.innerWidth,
        viewPortHeight = window.innerHeight
    }

    // older versions of IE
    else {
        viewPortWidth = document.getElementsByTagName('body')[0].clientWidth,
        viewPortHeight = document.getElementsByTagName('body')[0].clientHeight
    }

    return [viewPortWidth, viewPortHeight];
}

function getLines() {
    var onScreen = [];
    var viewPort = getViewport();
    // TODO: header & footer
    var all = document.getElementsByTagName("*");

    var vert = {};
    var horz = {};

    vert["0"] = 0;
    vert["" + viewPort[1]] = viewPort[1];
    horz["0"] = 0;
    horz["" + viewPort[0]] = viewPort[0];
    for (i = 0 ; i < all.length ; i++) {
        var e = all[i];
        // TODO: Get all client rectangles
        var rect = e.getBoundingClientRect();
        if (rect.width < 1 && rect.height < 1) continue;

        var left = Math.floor(rect.left);
        var top = Math.floor(rect.top);
        var right = Math.floor(rect.right);
        var bottom = Math.floor(rect.bottom);

        if (top > 0 && top < viewPort[1]) {
            vert["" + top] = top;
        }
        if (bottom > 0 && bottom < viewPort[1]) {
            vert["" + bottom] = bottom;
        }
        if (right > 0 && right < viewPort[0]) {
            horz["" + right] = right;
        }
        if (left > 0 && left < viewPort[0]) {
            horz["" + left] = left;
        }
    }

    hCoords = [];
    vCoords = [];
    //TODO: 
    for (var v in vert) {
        vCoords.push(vert[v]);
    }

    for (var h in horz) {
        hCoords.push(horz[h]);
    }

    return [hCoords, vCoords];
}

function getAreaPortions() {
    var portions = {}
    var lines = getLines();

    var hCoords = lines[0];
    var vCoords = lines[1];

    for (i = 1 ; i < hCoords.length ; i++) {
        for (j = 1 ; j < vCoords.length ; j++) {
            var portion = new AreaPortion(hCoords[i - 1], vCoords[j - 1], hCoords[i], vCoords[j]);
            portions[portion.getName()] = portion;
        }
    }

    return portions;
}

Answer 1

Try

var res = [];
$("body *").each(function (i, el) {
    if ((el.getBoundingClientRect().bottom <= window.innerHeight 
        || el.getBoundingClientRect().top <= window.innerHeight)
        && el.getBoundingClientRect().right <= window.innerWidth) {
            res.push([el.tagName.toLowerCase(), el.getBoundingClientRect()]);
    };
});

jsfiddle http://jsfiddle.net/guest271314/ueum30g5/

See Element.getBoundingClientRect()

$.each(new Array(180), function () {
    $("body").append(
    $("<img>"))
});

$.each(new Array(180), function () {
$("body").append(
$("<img>"))
});

var res = [];
$("body *").each(function (i, el) {
if ((el.getBoundingClientRect().bottom <= window.innerHeight || el.getBoundingClientRect().top <= window.innerHeight)
    && el.getBoundingClientRect().right <= window.innerWidth) {
    res.push(
    [el.tagName.toLowerCase(),
    el.getBoundingClientRect()]);
    $(el).css(
        "outline", "0.15em solid red");
    $("body").append(JSON.stringify(res, null, 4));
    console.log(res)
};
});

body {
    width : 1000px;
    height : 1000px;
}
img {
    width : 50px;
    height : 50px;
    background : navy;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>

Answer 2

I don't know if the performance will be sufficient (especially on a mobile device), and the result is not quite a rectangle-set as you requested, but did you consider using a bitmap to store the result?

Note some elements may have 3d css transform (eg. skew, rotate), some elements may have border radius, and some elements may have invisible background - if you want to include these features as well for your "element from pixel" function then a rectangle set can't help you - but the bitmap can accommodate all of the visual features.

The solution to generate the bitmap is rather simple (I imagine... not tested):

1. Create a Canvas the size of the visible screen.
2. iterate over all the elements recursively, sorted by z-order, ignore hidden
3. for each element draw a rectangle in the canvas, the color of the of the rectangle is an identifier of the element (eg. could be incremental counter). If you want you can modify the rectangle based on the visual features of the element (skew, rotate, border radius, etc...)
4. save the canvas as lossless format, eg png not jpg
5. send the bitmap as the meta data of elements on screen

To query which element is at point (x,y) you could check the color of the bitmap at pixel (x,y) and the color will tell you what is the element.