Случайные, не перекрывающиеся максимальные ширины divs, даже размерные по строкам

Question

У меня сложная проблема. Я пытаюсь случайным образом дивы разной высоты с условиями, которые

1. нет дивы перекрытия,
2. дивы по той же «х-линии» имеют одинаковую ширину, и
3. дивы занимают максимум доступная ширина без нарушения условия 2.

Я сохраняю значения для каждого div, когда я их создаю. Предотвращение дублирования легко, я в основном перебирает все дивы и проверить:

if (obj1.y < obj2.x && obj2.x < obj1.y) 

Однако, все становится сложнее, когда у меня есть несколько встречных дивов. Скажем, у меня есть два не сталкиваясь див (полная ширина):

Вот ссылка на иллюстрацию (не может включать в себя изображения без репутации :()

https://dl.dropboxusercontent.com/u/23220381/divs.png

Где Div1.width = div2 .width = Div3.width.

Мои первые попытки создать алгоритм не работают. В принципе, когда я добавляю div, я обнаруживаю, сколько коллизий существует. В случае Div3 он сталкивается с двумя другими div, но поскольку Div1 и Div2 не сталкиваются, мне нужно всего лишь увеличить ширину на 1/2, а не 1/3. Я могу исправить алгоритм, проверив, будут ли Div1 и Div2 co но я понятия не имею, как обобщить это на n Div.

Любая помощь будет высоко ценится :)

EDIT: Добавлено изображение, чтобы попытаться проиллюстрировать базовый сценарий :)

Answer 1

Я использую «найти пустые коробки» алгоритм, то, как здесь: http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529

Шаг1: Разделите экран на сетки, например

var screenWidth = 1360, 
    screenHeight = 900; 
var unitHeight = 10, 
    unitWidth = 10; 
var X_grids_count = screenWidth/unitWidth; 
var Y_grids_count = screenHeight/unitHeight; 

Шаг 2: Определение 2-мерный массив, и сделать стоимость всех сетей как 0, например,

GridArray = []; 
for(i=0;i<X_grids_count;i++) 
{ 
    GridArray[i] = []; 
    for(j=0;j<Y_grids_count;j++) 
    { 
     GridArray[i][j] = 0;  
    } 
} 

Шаг 3: Когда вы помещаете объект на экране, сделать значение занятых сеток в 1, например,

//Get the width and length of the object 
... 
//Get the position of the object 
... 
//Calculate how many grids in X-coordinate 
... 
//Calculate how many grids in Y-coordinate 
... 
//Calculate the start grids 
... 
//Use a for loop to make the value of the occupied grids into 1 

Шаг 4: Когда вы поставите новый объект на экране, сканировать все доступные сетки (значение сетки является 0)

//Scan from the first grid, check if all grids within the square that the new object occupies are available 
... 
//Get all available squares in the screen. You can make all startpoints(grids) as candidates 
... 
//Calculate the best one through all candidates based on your constraints, e.g. the shortest distance 
... 
//Convert the index of grids to actual pixel and put the object on that position 
... 
//Set the value of the occupied grids into 1 

Совершено