Calculate distance to move a box to remove interse

2019-08-28 23:35发布

问题:

I have two boxes that are overlapping and I want to figure out how to move one to remove the intersection.

I defined a vector from the center of one box to the other and move one box along that line, but that may be further than it needs to move, or may not be far enough. So I think what I need to do is figure out which corner of the stationary box lines closest to the line between the centers and then figure out how far along that line (or possibly projecting beyond that line) that corner would be. Then I can multiple my vector by that amount, but I'm having trouble wrapping my head around it.

Here's what I have at the moment, I'm adding items with an x,y,width and height property to a list and as I add each item, I'm checking for intersections with items already in the list. If an intersection is found, I try to move the new item and then try again:

function BoxList() {
    var self = this;
    var boxes = [];

    self.add = function(item, iteration) {
        // check intersections with existing boxes
        iteration = iteration || 0;
        if (iteration < 5) {
            for (var i=0; i < boxes.length; i++) {
                if (doesIntersect(getBounds(item),getBounds(boxes[i]))) {
                    item.elem.addClass("overlapped");
                    // Find vector from mid point of one box to the other
                    var centerA = { x: item.x + item.width / 2, y: item.y + item.height / 2 };
                    var centerB = { x: boxes[i].x + boxes[i].width / 2, y: boxes[i].y + boxes[i].height / 2 };
                    var line = { x1 : centerA.x, y1 : centerA.y, x2 : centerB.x, y2 : centerB.y };
                    var vector = { x : line.x1 - line.x2, y: line.y1 - line.y2 };
                    item.x = item.x + vector.x;
                    item.y = item.y + vector.y;
                    item.elem.offset({ left: item.x , top: item.y });       // TODO: calculate size of move needed
                    return self.add(item, iteration + 1);
                }
            }
        }
        boxes.push(item);
    }

    function getBounds(item) {
        return { x1: item.x, x2: item.x + item.width, y1: item.y, y2: item.y + item.height };
    }

    function doesIntersect(a,b) {
        return a.x1 < b.x2 && a.x2 > b.x1 && a.y1 < b.y2 && a.y2 > b.y1;
    }
}

Here's a simple fiddle

Click move to attempt to arrange the two boxes, note that the overlapping box is moved twice and gets moved further than it really needs to.

Any thoughts? Suggestions on better ways to approach this also greatly appreciated.

回答1:

As I read it now you calculate the centers of both boxes and use those two points to make the vector that pushes one of the boxes. That's the wrong vector. If you place the boxes right on top of each other that vector will be (0,0). If the boxes only just clip each other the vector will be at it's highest possible value.

You can see this in action with the ghosts. First it gets pushed only a little bit, then it gets pushed a lot.

Instead the vector you need should be based on the size of the overlap. If the overlap is 20px by 30px your vector is (+20,+30)

var vector = {
    x: Math.min(box1.x + box2.width, box2.x + box2.width) - Math.max(box1.x, box2.x),
    y: Math.min(box1.y + box2.height, box2.y + box2.height) - Math.max(box1.y, box2.y)
}

vector.x is the top-right of the bounding box minus the bottom-left of the bounding box. Idem for vector.y.

This moves the box by exactly the right amount: http://jsfiddle.net/x8MT3/2/

I added a 3rd box pair that needs 2 iterations, probably the top box should move the other way. The vector as I've set it up is always (+,+), you can do your center point calculation to determine which sign each direction should have.