Algorithm to find space for an object within a 2d area

Question

I'm building a website which uses jQuery to allow users to add widgets to a page, drag them around and resize them (the page is fixed width and infinite height.) The issue that I'm having is that when adding a new widget to the page I have to find a free space for it (the widgets cannot overlap and I'd like to favour spaces at the top of the page.)

I've been looking at various packing algorithms and none of them seem to be suitable. The reason why is that they are designed for packing all of the objects in to the container, this means that all of the previous rectangles are laid out in a uniform way. They often line up an edge of the rectangle so that they form rows/columns, this simplifies working out what will fit where in the next row/column. When the user can move/resize widgets at will these algorithms don't work well.

I thought that I had a partial solution but after writing some pseudo code in here I’ve realized that it won’t work. A brute force based approach would work, but I'd prefer something more efficient if possible. Can anyone suggest a suitable algorithm? Is it a packing algorithm that I'm looking for or would something else work better?

Thanks

Answer 1

Ok, I've worked out a solution. I didn't like the idea of a brute force based approach because I thought it would be inefficient, what I realized though is if you can look at which existing widgets are in the way of placing the widget then you can skip large portions of the grid.

Here is an example: (the widget being placed is 20x20 and page width is 100px in this example.)

This diagram is 0.1 scale and got messed up so I've had to add an extra column

*123456789A*
1+---+ +--+1
2|   | |  |2
3|   | +--+3
4|   |     4
5+---+     5
*123456789A*

1. We attempt to place a widget at 0x0 but it doesn't fit because there is a 50x50 widget at that coordinate.
2. So we then advance the current x coordinate being scanned to 51 and check again.
3. We then find a 40x30 widget at 0x61.
4. So we then advance the x coordinate to 90 but this doesn't leave enough room for the widget being placed so we increment the y coordinate and reset x back to 0.
5. We know from the previous attempts that the widgets on the previous line are at least 30px high so we increase the y coordinate to 31.
6. We encounter the same 50x50 widget at 0x31.
7. So we increase x to 51 and find that we can place a widget at 51x31

Here is the javascript:

function findSpace(width, height) {
    var $ul = $('.snap-layout>ul');
    var widthOfContainer = $ul.width();
    var heightOfContainer = $ul.height();
    var $lis = $ul.children('.setup-widget'); // The li is on the page and we dont want it to collide with itself

    for (var y = 0; y < heightOfContainer - height + 1; y++) {
        var heightOfShortestInRow = 1;
        for (var x = 0; x < widthOfContainer - width + 1; x++) {
            console.log(x + '/' + y);
            var pos = { 'left': x, 'top': y };
            var $collider = $(isOverlapping($lis, pos, width, height));
            if ($collider.length == 0) {
                // Found a space
                return pos;
            }

            var colliderPos = $collider.position();
            // We have collided with something, there is no point testing the points within this widget so lets skip them
            var newX = colliderPos.left + $collider.width() - 1; // -1 to account for the ++ in the for loop
            x = newX > x ? newX : x; // Make sure that we are not some how going backwards and looping forever

            var colliderBottom = colliderPos.top + $collider.height();
            if (heightOfShortestInRow == 1 || colliderBottom - y < heightOfShortestInRow) {
                heightOfShortestInRow = colliderBottom - y; // This isn't actually the height its just the distance from y to the bottom of the widget, y is normally at the top of the widget tho
            }
        }
        y += heightOfShortestInRow - 1;
    }

    //TODO: Add the widget to the bottom
}

Here is the longer and more less elegant version that also adjusts the height of the container (I've just hacked it together for now but will clean it up later and edit)

function findSpace(width, height,
        yStart, avoidIds // These are used if the function calls itself - see bellow
    ) {
    var $ul = $('.snap-layout>ul');
    var widthOfContainer = $ul.width();
    var heightOfContainer = $ul.height();
    var $lis = $ul.children('.setup-widget'); // The li is on the page and we dont want it to collide with itself

    var bottomOfShortestInRow;
    var idOfShortestInRow;

    for (var y = yStart ? yStart : 0; y <= heightOfContainer - height + 1; y++) {
        var heightOfShortestInRow = 1;
        for (var x = 0; x <= widthOfContainer - width + 1; x++) {
            console.log(x + '/' + y);
            var pos = { 'left': x, 'top': y };
            var $collider = $(isOverlapping($lis, pos, width, height));
            if ($collider.length == 0) {
                // Found a space
                return pos;
            }

            var colliderPos = $collider.position();
            // We have collided with something, there is no point testing the points within this widget so lets skip them
            var newX = colliderPos.left + $collider.width() - 1; // -1 to account for the ++ in the for loop
            x = newX > x ? newX : x; // Make sure that we are not some how going backwards and looping forever

            colliderBottom = colliderPos.top + $collider.height();
            if (heightOfShortestInRow == 1 || colliderBottom - y < heightOfShortestInRow) {
                heightOfShortestInRow = colliderBottom - y; // This isn't actually the height its just the distance from y to the bottom of the widget, y is normally at the top of the widget tho
                var widgetId = $collider.attr('data-widget-id');
                if (!avoidIds || !$.inArray(widgetId, avoidIds)) { // If this is true then we are calling ourselves and we used this as the shortest widget before and it didnt work
                    bottomOfShortestInRow = colliderBottom;
                    idOfShortestInRow = widgetId;
                }
            }
        }
        y += heightOfShortestInRow - 1;
    }

    if (!yStart) {
        // No space was found so create some
        var idsToAvoid = [];

        for (var attempts = 0; attempts < widthOfContainer; attempts++) { // As a worse case scenario we have lots of 1px wide colliders
            idsToAvoid.push(idOfShortestInRow);

            heightOfContainer = $ul.height();
            var maxAvailableRoom = heightOfContainer - bottomOfShortestInRow;
            var extraHeightRequired = height - maxAvailableRoom;
            if (extraHeightRequired < 0) { extraHeightRequired = 0;}

            $ul.height(heightOfContainer + extraHeightRequired);

            var result = findSpace(width, height, bottomOfShortestInRow, idsToAvoid);
            if (result.top) {
                // Found a space
                return result;
            }

            // Got a different collider so lets try that next time
            bottomOfShortestInRow = result.bottom;
            idOfShortestInRow = result.id;

            if (!bottomOfShortestInRow) {
                // If this is undefined then its broken (because the widgets are bigger then their contianer which is hardcoded atm and resets on f5)
                break;
            }
        }

        debugger;
        // Something has gone wrong so we just stick it on the bottom left
        $ul.height($ul.height() + height);
        return { 'left': 0, 'top': $ul.height() - height };

    } else {
        // The function is calling itself and we shouldnt recurse any further, just return the data required to continue searching
        return { 'bottom': bottomOfShortestInRow, 'id': idOfShortestInRow };
    }
}


function isOverlapping($obsticles, tAxis, width, height) {
    var t_x, t_y;
    if (typeof (width) == 'undefined') {
        // Existing element passed in
        var $target = $(tAxis);
        tAxis = $target.position();
        t_x = [tAxis.left, tAxis.left + $target.outerWidth()];
        t_y = [tAxis.top, tAxis.top + $target.outerHeight()];
    } else {
        // Coordinates and dimensions passed in
        t_x = [tAxis.left, tAxis.left + width];
        t_y = [tAxis.top, tAxis.top + height];
    }

    var overlap = false;

    $obsticles.each(function () {
        var $this = $(this);
        var thisPos = $this.position();
        var i_x = [thisPos.left, thisPos.left + $this.outerWidth()]
        var i_y = [thisPos.top, thisPos.top + $this.outerHeight()];

        if (t_x[0] < i_x[1] && t_x[1] > i_x[0] &&
             t_y[0] < i_y[1] && t_y[1] > i_y[0]) {
            overlap = this;
            return false;
        }
    });
    return overlap;
}