logo标签列表

在二维区域内寻找物体空间的算法

javascriptjqueryalgorithm
3
我正在构建一个网站，使用jQuery允许用户向页面添加小部件，拖动它们并调整大小（页面固定宽度，无限高）。我的问题是当我向页面添加新的小部件时，我必须要找到一个空闲的位置放它（小部件不能重叠，并且我想优先放在页面顶部的空间）。
我一直在研究各种排列算法，但似乎没有一个合适的。原因是它们都是用于将所有对象放入容器中，这意味着所有以前的矩形都以统一的方式布局。它们通常会对齐矩形的边缘，以形成行/列，这样可以简化计算下一行/列的放置位置。当用户可以自由移动/调整小部件时，这些算法效果不佳。
我认为我有部分解决方案，但在这里编写了一些伪代码后，我意识到它行不通。基于蛮力的方法可以解决问题，但如果可能的话，我更喜欢一些更有效的方法。有人能提供一个合适的算法吗？我需要寻找的是一个装箱算法，还是其他算法更适合？谢谢。
1
你可以创建一个图形文件，以文本方式描述你的情况（小部件是图形节点，邻域距离是边缘），并让GraphViz（http://www.graphviz.org/）找到解决方案。另一个思路是尝试力导向算法。寻找“弹簧嵌入器”方法。 - Axel Kemper
谢谢Axel，我看了一下，但是这个数学对我来说太难了。 - JoeS
1个回答
4

好的，我已经想出了一个解决方案。我不喜欢基于暴力方法的想法，因为我认为这种方法效率不高。但我意识到，如果你可以查看哪些现有的小部件挡住了放置小部件的位置，那么你可以跳过网格的大部分。

以下是一个示例：（在此示例中，要放置的小部件为20x20，页面宽度为100px。）

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. 我们试图将一个小部件放置在0x0处，但由于该坐标处有一个50x50的小部件，所以无法放置。
  2. 因此，我们将当前正在扫描的x坐标推进到51并再次检查。
  3. 然后，我们发现在0x61处有一个40x30的小部件。
  4. 因此，我们将x坐标推进到90，但这不足以留出放置小部件的空间，因此我们将y坐标增加并将x重置为0。
  5. 我们知道前一行上的小部件至少有30px高，因此我们将y坐标增加到31。
  6. 我们在0x31遇到相同的50x50小部件。
  7. 因此，我们将x增加到51，并发现可以在51x31处放置小部件。

以下是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
}

这里是更长、不太优雅的版本，它还调整了容器的高度（我现在只是粗略地拼凑起来，稍后会进行清理和编辑）

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;
}
这个算法的时间复杂度是多少？ - blackgreen
最糟糕的情况是 $O(m^2n^2)$，其中 m 是行数，n 是列数。这是在所有小部件大小都是1x1且可以连续放置的情况下。考虑到 1+2+3+...+n为 O(n^2)，1+2+...+mxn = O((mxn)^2) = O(m^2 n^2)。 - Sentient
请参阅此讨论 https://dev59.com/L2Af5IYBdhLWcg3wZSFI - Sentient
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接