Здравствуйте!

У каждого прямоугольника есть координаты X,Y, длина и ширина.

Как определить определить расстояния (см. рисунок) ?





Это сообщение отредактировал(а) SANCHO123 - 29.4.2012, 08:04

Присоединённый файл ( Кол-во скачиваний: 24 )
 1.jpg 30,14 Kb

А по какому принципу расположены прямоугольники? По какому принципу выбирается линия вдоль которой проводится измерение?

Если прямоугольники расположены без какого-то принципа, а линия определяется заданной точкой, то, наверное, как-то так:

Для случая определения расстояния по вертикали:
Имеем набор прямоугольников, определяемых точками двух противоположных углов (xA,yA) - верхний левый, (xB,yB) - нижний правый.  (X,Y) - координаты точки.
1. Исключаем из рассчета все прямоугольники, у которых xA>X, то есть лежащие правее точки.
2. Исключаем из рассчета все прямоугольники, у которых xB<X, то есть лежащие левее точки.
3. Дальше работаем только с оставшимися прямоугольниками.
4. Прямоугольники сортируем по yA, например.
5. Находим величины yA(i) лежащие ближе всего к Y с большей, например, стороны. Условия можно записать как Y<yA(i) и yA(i)-Y=min
6. Ответом будет разность yA(i) - yB(i-1)

Есть варианты:

• Если после п.2 прямоугольников не осталось - пространство свободно по всей высоте.
• Если найденый индекс i указывает первый элемент массива - пространство свободно до верха.
• Если индекс i соответствующий условиям найти не удается - пространство свободно до низа.

При этом предполагается что (X,Y) заведомо взята на пустом пространстве или на стороне прямоугольника с этим пространством граничащей. Иначе надо добавлять проверки и другие операции после пункта 2.

От нижней стороны (случай прямоугольника 1), от правой стороны (случай прямоугольника 2 и 4).
Вертикально - область с наибольшей шириной. Горизонтально - область с наибольшей высотой.

Может быть есть вариант и лучше.
Задача: покрыть свободную область прямоугольниками. 

Эта часть пустой области должна определяться от прямоугольника 1.


Эта от 4

Правильно ли я понимаю, что нужно найти область, в которую можно вписать следующий самый большой прямоугольник?

Тогда встает вопрос - критерий того что есть "самый большой"? Самый большой по площади? Или может по наибольшей стороне?

Нужно просто найти пустые области.

Сначала я хотел описать пустую область замкнутым полигоном. Но я не знаю как это сделать. 
Потом решил описать пересекающимися прямоугольниками. 

А что если проверить каждую точку на принадлежность прямоугольникам?

Получится массив точек пустой области.

Возможно ли будет из этого массива получить пустые прямоугольники?  

В принципе можно конечно. Но будут две заморочки.
1. Это будет не самый быстрый в мире алгоритм.
2. Если в конечном счете нужны будут все-таки прямоугольники получится много частично накладывающихся прямоугольников. От каждой точки, попавшей в чистое поле можно построить прямоугольник по описанному выше алгоритму. Но прямоугольники от разных точек получатся разные.

Впрочем, если это не пугает, можно так и поступать:
Попозже подумаю как сделать такой алгоритм чуть более разумным.

Это сообщение отредактировал(а) _Y_ - 29.4.2012, 20:24

Его можно будет распараллелить?  



После размещение нового прямоугольника пустые области будут формироваться заново. Потому они могут накладываться.

X,Y,W,H (столбец, строка, ширина, высота).

Пример:
00000
00000
10100
10100

Результат:
0,0,5,2
1,0,1,4
3,0,2,4

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

И спасибо за ответы 

Если не задавать условия что сначала выбирается самый большой из возможных прямоугольников, и согласиться с поточечным проходом (достаточно по одоной из осей), то можно попробовать так:

Имеем:
Поле точек-пикселей размером Xmax на Ymax 
Массив прямоугольников M в котором каждый прямоугольник определяется точками (xA,yA),(xB,yB)

1. Задаем начальное значение Y=0
2. Копируем из массива M во временный массив m все члены, соответствующие условию (yA<Y)AND(yB>Y). То есть выбираем все прямоугольники лежащие на горизонтали с координатой Y.
3. Сортируем массив  m по xA
4. Ищем "зазор" в массиве  m, т.е. любую пару соседних прямоугольников, для которой xB(i)< xA(i+1), где i - индекс прямоугольника в массиве m. Зазорами также будут случаи 0< xA(1) и xB(max)<Xmax.
5. Если ни одного зазора не найдено значит прямоугольники плотно упакованы вдоль выбранной горизонтали. Идем к пунту 7.
6. Если зазор найден - строим в нем прямоугольник. Добавляем этот прямоугольник в массивы  M и  m. Возвращаемся к пункту. 3.
7. Выбираем новую горизонталь Y=Y+1. 
8. Если Ymax<Y рассчет окончен. Если нет - возвращаемся к пунту 2 для обработки новой горизонтали.

Поле должно заполняться не-накладывающимися друг на друга прямоугольниками. Условие - исходные прямоугольники тоже не накладываются друг на друга. 

Алгортим можно оптимизировать конечно. Это я так - навскидку придумал.

Хороший алгоритм. Спасибо  
Но в процессе работы алгоритма нужны пересекающиеся прямоугольники, чтобы увеличить вероятность укладки прямоугольника в одну из пустых областей.

Не понял я что-то. Может как-то другими словами до меня лучше дойдет. При чем здесь вероятность?

Я нарисую.

При таком расположении по предложенному алгоритму будет 3 области, правильно?


Но не в одну из этих областей не поместиться прямоугольник изображенный зеленым цветом:


В случае перекрывающихся прямоугольников он поместится



Это сообщение отредактировал(а) SANCHO123 - 30.4.2012, 22:14

Решил попробовать самое простое в реализации решение: выделение прямоугольных областей из матрицы. Алгоритм получится очень очень медленным.

Х=0...(W-1)
begin
Поиск последовательности нулей по вертикали.
Если найдена такая последовательность, запомнить координаты начала и конца.
Проверить, если ли такая же последовательность левее (с такими же значениями Y начала и конца)
Если есть - проверить еще левее, если нет -запомнить координаты.
Перейти к следующей последовательности.
end

Аналогично по горизонтали.
\\\\
Получается очень много прямоугольников лежат в друг друге.
После работы алгоритма эти прямоугольники нужно удалить. Проверка на принадлежность очень простая, но для большего количества прямоугольников данная операция занимает много времени. Потому таких прямоугольников не должно быть (желательно).

Это сообщение отредактировал(а) SANCHO123 - 30.4.2012, 22:29

Если я правильно понимаю, речь идет о решении задачи оптимальной упаковки. Я этой задачей специально не занимался, но как-то раз оппонировал диссертацию на эту тему. В большинстве случаев делают так. 
1. В начале есть пустая область - весь контейнер.
2. При добавлении нового груза (прямоугольника) все пустые области, содержащие этот груз либо
    2.1. исчезают - вся область закрыта прямоугольником
    2.2. уменьшаются - крайняя часть одной из областей закрыта грузом
    2.3. разбивается на несколько пустых областей - угол груза попал в пустую область.
3. После первичной обработки проводится объединение некоторых пустых областей.
4. переход к следующему грузу.

Большинство алгоритмов различаются именно способом учета пустых областей.
Думаю, что для начала будет полезно ознакомиться с имеющимся опытом в данной области.

Нет, это не то, о чем я думал. Ведь могут быть и такие варианты:

То есть алгоритм находит только первое попавшееся место, в которое можно вставить прямоугольник (красная линия - она вообще-то должна идти по верху свободного места, но так ее виднее). А уж как от него тянуть этот прямоугольник вниз - дело ваше. Но хотите - придумаю.

Кстати, в условии я писал что алгоритм не пытается вставить самый большой из возможных прямоугольников