Layering intersecting elements with jQuery

I have a page with draggable/droppable elements that once dropped need to calculate their left position and width in regards to other draggables that they may be touching.

This isn't too hard in and of itself, but where I'm really having trouble is getting them to fill in empty space. How do I get the draggables to fill in the empty space without doubling on top of each other?

// $t is the element being added/dropped. 
// nd refers to New Dimensions, IE, the new dimensions for $t
// existingDivs gets any DIV's that have already been added to the dom
var $t = $(this), nd = {t:$t.position().top, h:$t.height(), l: 0, w: 95},
  existingDivs = $('#container .subContainer .draggable'), intersectArr = [],
  nonIntersectArr = [], finalArr = [];

// If there are no DIV's in the DOM you dont need to check if they intersect.
if (existingDivs.length > 0) {
// Find the DIV's that Intersect with the one being added
  intersectArr = $.grep(existingDivs, function(val,num){
    // xd is Existing Dimensions, for the current item being checked
    // verse the one being added.
    var $t2 = $(val), xd = {h:$t2.height(), w:parseFloat($t2.css('width')),
    l:parseFloat($t2.css('left')), t:$t2.position().top};
    // If they intersect add it to this array
    return ((xd.t <= nd.t && xd.t+xd.h > nd.t) ||
    (nd.t <= xd.t && nd.t+nd.h > xd.t));
  });
// Find the DIV's that DO NOT Intersect with the one being added
  nonIntersectArr = $.grep(existingDivs, function(val,num){
    // xd is Existing Dimensions, for the current item being checked
    // verse the one being added.
    var $t2 = $(val), xd = {h:$t2.height(), w:parseFloat($t2.css('width')),
    l:parseFloat($t2.css('left')), t:$t2.position().top};
    // If they DO NOT intersect add it to this array
    return ((xd.t > nd.t && xd.t > nd.t+nd.h) ||
    (nd.t > xd.t && nd.t > xd.t+xd.h));
  });
// For every element that does not intersect, check it verse the ones that do
  $(nonIntersectArr).each(function(){
    // nid is Non Intersecting Dimensions
    var $t2 = $(this), c = 0, nid = {h:$t2.height(),
    w:parseFloat($t2.css('width')),
    l:parseFloat($t2.css('left')), t:$t2.position().top};
    $(intersectArr).each(function(){
    // id is Intersecting Dimensions
      var $t3 = $(this), id = {h:$t3.height(), w:parseFloat($t3.css('width')),
      l:parseFloat($t3.css('left')), t:$t3.position().top};
    // if the non intersecting hits one that is intersecting, then there is no space
    // beneath/near it, so we add it to the final intersecting array then increment c
      if((id.t <= nid.t && id.t+id.h > nid.t) ||
      (nid.t <= id.t && nid.t+nid.h > id.t)){ finalArr.push(this); c++; }
      else { finalArr.push(this); }
    });
    // if c has been incremented, we cant use this nonIntersect, so add it to the final
    if(c > 0) { finalArr.push(this); }
  });
  // make sure all items in the final Array are unique
  finalArr = $.unique(finalArr);
  // iterate over the final array, processing the dimensions of each element in the
  // array layering them so you can see each one
  $(finalArr).each(function(num){
    // xd is Existing Dimensions, for the current item being checked
    // verse the one being added.
    var $t2 = $(this), xd = {h:$t2.height(), w:parseFloat($t2.css('width')),
    l:parseFloat($t2.css('left')), t:$t2.position().top};
    if(((xd.t <= nd.t && xd.t+xd.h > nd.t) ||
    (nd.t <= xd.t && nd.t+nd.h > xd.t))) {
      if(nd.l == xd.l){
        nd.w = ((95/(finalArr.length+1))*1.5);
        xd.l = ((nd.w)*(num));
        $(finalArr).each(function(ci){
          $(this).css({left:((nd.w*ci)*0.58)+'%',
          width:((95/(finalArr.length+1))*1.5)+'%'});
          nd.l = ((nd.w*ci)*0.58);
        });
      }
    }
  });
}
// Add the New Element to the container and position accordingly.
nd.l = ((nd.l/finalArr.length)*(finalArr.length+1))+'%';
nd.w = nd.w+'%';
$('#container .subContainer').append('<d开发者_Python百科iv style="top:'+nd.t+'px;left:'+nd.l+
';width:'+nd.w+';height:'+nd.h+'px;" class="dragId_'+$t.attr('id')+
' draggable"><div class="title">'+$t.attr('title')+'</div></div>');

Any suggestions/help would be much appreciated. Thanks.

Here's the algorithm for what you need to do:

1. While there are shapes touching, figure out the rightmost shape (the one with the biggest right x-coordinate) that is touching another shape. Move it so its left edge is just right of the rightmost shape it was just touching.
2. While there are shapes not next to something to the left of them, figure out the shape with the smallest left x-coordinate that is not next to something to the left of it. Move it so its left edge is just right of the shape with the largest right x-coordinate that lies in the y-range of the object.

Simple enough? Well, here's the simplified version:

1. While there are shapes touching each other, move the rightmost one so it isn't touching any other shapes.
2. While there are shapes not snuggled up to each other, move the leftmost one so it is snuggled up to the closest shape.

Edit: For example...

Suppose I took square 3 and plopped it on top of square 1 and square 2:

1111   44
1111   44
1133333
1133333
  33333
  3333322
  3333322
     2222
     2222

Step 1. Find the rightmost shape that's intersecting something. In this case, that's shape 2. Move it right of what it's intersecting.

1111   44
1111   44
1133333
1133333
  33333
  333332222
  333332222
       2222
       2222

Are there shapes touching now? Yes, and the rightmost one is shape 3. Move it right of the shape it's touching, shape 1:

1111   44
1111   44
111133333
111133333
    33333
    3333322
    3333322
       2222
       2222

Are there shapes touching now? Yes, and the rightmost one is shape 2. Move it right of the shape it's touching, shape 3:

1111   44
1111   44
111133333
111133333
    33333
    333332222
    333332222
         2222
         2222

Are there shapes touching now? No. So we're done step 1.

Step 2: Find the leftmost shape that's not snuggled up to anything. In this case, the leftmost one not snuggled up to anything is shape 4. Move it left so it's just right of the rightmost shape left of it that exists at the same y-coordinates as it:

111144
111144
111133333
111133333
    33333
    333332222
    333332222
         2222
         2222

Anything not snuggled up to anything? Nope! So you're done!

As you can see, there's basically an expansion phase and a contraction phase. You do the expansion phase right to left so that nothing gets expanded right through something else. You do the contraction phase left to right so nothing gets contracted through something else.