Здравствуйте! Передо мной стоит задача, которая сводится к взаимному выравниванию между собой прямоугольников на плоскости. Что то наподобие верстки газетных колонок. Исходное расположение задано, необходимо исправить мелкие пересечения, подогнать размеры сходных элементов и провести выравнивание.
Вот некоторые примеры для более ясного понимания задачи (то, что должно получиться):

Произошло взаимное выравнивание между элементами.

Здесь показано приведение размера подобных элементов (красный с зеленым) и последующее выравнивание.

В этом случае четыре квадрата подравниваются относительно друг друга и равномерно распределяются по ширине.

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

Такое же как и первое, но более сложное.
Уже долгое время пытаюсь решить данную задачу, придумал и реализовал несколько разных подходов, однако в каждом из них есть недочеты, нет универсальности, а сроки поджимают. У меня уже все мысли закончились, хожу изо дня в день по кругу не приближаясь к результату.
Возможно кто то сталкивался с чем то подобным или «видит» решение? К какому общему типу задач ближе всего эта, возможно я плохо искал и что то уже реализовано?


Это сообщение отредактировал(а) overcoder - 11.1.2011, 21:13

У меня ни одна картинка не открылась

Короче, выравнивание (и размеров, и положения) по сетке... но что-то мне подсказывает, что ( особенно в последних двух случаях) ты хочешь СЛИШКОМ много интеллекта.

Bitter, перезалил на radikal, ipicture вечером отваливается
Akina, слишком много мне не надо, достаточно будет ровно столько что бы работало 

На самом деле я пытался разбить это на 3 подзадачи.
1) установка размеров сходных элементов (те, которые стоят в одной строке или столбце, грубо можно сделать усреднение)
 проблемы:
а) на один элемент может влиять несколько других
б) зацикливание когда к примеру 4 элемента стоят по вершинам квадрата, и каждый влияет на 2 других, т.е. их надо идентифицировать и 
обработать разово все, а не по очереди
в) еще что то
2) убрать нахлесты (или коллизии)
проблемы:
а) если раздвигать одни элементы, они могут залезть на другие, тем самым еще более усугубив задачу
б) определение направления и силы сдвига
в) еще что то
3) после всего этого выравнивание по сетке
проблемы тоже есть

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

Это сообщение отредактировал(а) overcoder - 11.1.2011, 21:20

в 1,2и 3   примере выбираем прямоугольник у которого наибольший габаритный размер. далее исходя из этого габаритного размера очерчиваем контур или периметр в котором будут вписаны все  прямоугольники. Затем боковые прямоугольники выравниваем по этому периметру. А  внутренние прямоугольники уже выравниваются после вычисления одинаковых зазоров.   

пример 5 в принципе тоже самое. только рисуются два периметра. в первый периметр так же размещаются  прямоугольники. Вторая строчка снизу.. там где три прямоугольника с мелким зазором . очерчиваем вторым периметром так, чтобы взлезли три прямоугольника. затем вычисляются одинаковые зазоры внутри первого периметра и центрируем( причем второй периметр считаем как будто-это один прямоугольник). Потом во втором периметре два мелких прямоугольника раздвигаются по периметру и также вычисляем зазор между ними.

Это сообщение отредактировал(а) миг - 11.1.2011, 22:54

миг, проследил каждый ваш шаг и полностью согласен - я бы делал точно так же.
Но, во-первых, у меня этих примером больше ста (контрольная выборка), а в перспективе - бесконечность.
Во-вторых то что вы написали - т.с. человеческий ход мыслей, причем для 123 один, для 5 другой.
Вы представляете как реализовать это в коде? Прямоугольников может быть не 5-6, а до 20, и простое разделение внешний-внутренний уже не пройдет.
Мне нужен алгоритм, который проанализировал бы картину и расставил бы элементы.
Тем не менее, спасибо за ответ и проявленный интерес.

Сначала разбейте всё на слои. Например, на рисунке 5 мы имеем два слоя, и второй (зелёные элементы) обрабатывается как однослойный, в габаритах включающего все его элементы блока первого слоя. Уже станет попроще.
Далее - не старайтесь двигать и ресайзить блоки. Наоборот, выделите разделяющие блоки отрезки (свободное пространство), и симметрируйте/выравнивайте именно их. При этом сначала выровняйте их по толщине, определите симметричные группы, а затем выстраивайте систему приоритетов - обработку начинайте с тех, которые лежат обеими концами на границе области, потом одним концом, потом ... в общем задайте систему приоритетов обработки - скажем считайте вес каждого конца отрезка как вес ближайшей внешней границы, уполовиненный столько раз, сколько на пути к нему поворотов. Завершив итерацию выравниваний, проверьте изменение размеров, если оно недопустимо - скорректируйте относительные веса линий пропорционально изменению площади или размера и повторите...

Появилась такая идея: (не уверен, что хорошая, но может ещё кого-нибудь натолкнёт на мысли)

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

Akina, очень интересная мысль, я не задумывался над тем что бы уравнивать промежутки - как то упустил этот вариант. Спасибо!!
По поводу симметрии хочу сказать что в большинстве случаев ее нет, просто в моих примерах которые рисовались от руки так получилось само 
Вот один из рабочих образцов, даю просто ссылкой, осторожно, 6 мегабайт
http://s002.radikal.ru/i198/1101/5d/7ed2b8e5ce1f.png
maxim1000, дело в том что правильного нет, к нему необходимо прийти, но там нужно уже вывести критерии "правильности". Либо я немного не понял что вы имели ввиду.

Подавляющее большинство образцов - симметричны или по крайней мере подобны хотя бы по одному из измерений.

На данном примере согласен, на многих есть симметрия. В целом сейчас просмотрел несколько, положим симметрия в некоторой степени присутсвует на 50%, в чистом виде на 10-15%
вопрос, будет ли это что то давать? не хочется "прикручивать" сюда симметрию если не ясны ее перспективы. Хотя уже на данный момент крутится пару идей с ее исплоьзованием.

overcoder, Можно ввести силы отталкивания и притяжения и "раздувания". Каждый прямоугольник отталкивается от соседей по квадратичному закону. каждый прямоугольник, если сила, действующая на сторону не выше чего-то, увеличивает свой размер в этом направлении. Все они ограничены прямоугольной "рамкой", противоположные стороны которой "стягиваются" по линейному закону. 
Отталкивание дает нам просвет между элементами.
Стягивание встраивает конструкцию в прямоугольник.
Раздувание устранят ненужные пробелы.

прямо как в реальной жизни   

вычисление конечного положения ведется как последовательность итераций. 
-- вычисляются все силы, действующие на прямоугольник и на каждую сторону, 
-- по окончании вычислений прямоугольники изменяют свое состояние(двигаются) все сразу, в соответствии с силами (в сторону и изменяя размер)
-- вычисление повторяется...

нужно ввести еще и "среду", которая будет мешать очень резким движениям, чтобы не было циклической тряски.

Довольно забавная возможность - просто напихать туда всяких фигурок и пусть оно само расставится как надо... если не понравилось расположение - можно "потрясти"

Добавлено через 3 минуты и 28 секунд
прямоугольник состоит из "сторон", для которых и нужно вычислять силы. У стороны есть "масса" - ее длина и центр тяжести - ее середина. На прямоугольник действует сила - сумма сил, действующих на его стороны.

ksnk, спасибо, очень ценная идея, надо обдумать!
Я реализовывал нечто подобное, с учетом физической среды, но только для избавления от коллизий, тоже в пределах ограниченной области.
Кстати сделал итерационно с отрисовкой и задержкой в 0.1 сек на кадом шаге  - очень инетерсно было наблюдать как куча элементов разъезжалась в разные стороны.

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

overcoder, Да я представляю как реализовать это в коде.. Для 1,2,3,5 используется один и тот же подход. Только для 5 как бы это сказать немного расширенный подход.. То о чем я говорил можно применить к любому количеству прямоугольников и квадратов.. Если у вас в перспективе бесконечность, то на это уйдет бесконечное количество времени.. Вы собираетесь до пенсии прямоугольники расставлять?

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

Это сообщение отредактировал(а) миг - 15.1.2011, 11:17

Я бы делал несколько проще и итерационно в комбинации с Монте Карло. Примерно так (многое из этого было высказано в предидущих сообщениях, но вразбивку):

Сначала описываем минимизируемую функцию F. Например, разность площадей зазора над и под объектом плюс разность площадей зазора слева и справа от объекта. Еще будем считать величину 
S=F(1)+F(2)+...+F(n) т.е. суммировать минимизируемые функци для всех объектов.

Теперь начинаем телодвижения:
1. Находим периметр - внешний контур - прямоугольник, за который объекты вылезать не должны. Если найти его трудно - делаем прямоугольник с запасом.
2. Заполняем углы ближайшими к ним объектами.
3. Двигаем каждый объект в сторону ближней линии периметра; но не позволяем объектам наезжать друг на друга. Таким образом расставляем внешние объекты по периметру. Внутренние объекты можно вообще не двигать на этом шаге, но тогда нужно сначала определить какие внешние, а какие внутренние - алгоритм усложняется.
4. Присваиваем объектам степени свободы: объекты, находящиеся в углах, двигаться права не имеют; объекты, соприкасающиеся с горизонтальными линиями периметра могут двигаться только по оси X; объекты, соприкасающиеся с вертикальными линиями периметра могут двигаться только по оси Y. Остальные (внутренние) объекты могут двигаться по двум осям.
5. Инициализируем иттерационный процесс рассчитав S.
6. Последовательно двигаем каждый объект в рамках его степеней свободы оптимизируя функцию F.
7. Считаем новое значение S и сравниваем с предидущим значением. Если значение уменьшилось идем к шагу 6. Если значение увеличилось (ухудшилось) идем к шагу 8. Если не изменилось - к шагу 8 или 9 не важно.
8. Возвращаем пложения объектов на один шаг назад.
9. Случайным образом изменяем последовательность работы с объектами, т.е. случайным образом перемешиваем массив объектов, не меняя их положения на картинке. Это делается для изменения последовательности работы с объектами. Переходим к пункту 6.

Работу алгоритма завершаем когда пункт 9 пройден заданное количество раз.

Алгоритм этот написан умозрительно - писать программу некогда к сожалению. Поэтому не знаю - может Монте Карло и излишество.  Серьезнее всего надо подойти к определению функции F. Как оптимизировать белые кантики вокруг объектов лучше всего знают верстальщики газет - эти вопросы зрительного восприятия они изучили задолго до появления компов.

Это сообщение отредактировал(а) _Y_ - 15.1.2011, 12:13

_Y_, Согласен.. но я думаю в третьем шаге можно определить внешние объекты по координатам углов прямоугольника.. Мне пришло в голову сам ограничивающий прямоугольник рассматривать как двумерный массив.. А координаты реальных прямоугольников записать в виде координат массива i,j и двигать все это дело внутри массива.. Причем для экономии памяти сам массив создавать не обязательно. 
Вот! В С++ создал класс прямоугольник и храню там информацию о количестве прямоугольников и их вершинах.. 

 и планирую двигаться по виртуальному массиву с помощью двух циклов for(int i=0; i<n;i++), for(int j=0;j<m;j++)


 

это я на работе в обеденный перерыв пытался набацать. правда я еще не доделал, но на мой взгляд должно выглядеть как то так))



Это сообщение отредактировал(а) миг - 15.1.2011, 14:04

миг, в C++ я, к сожалению, не силен. Что касается пункта 3, то я описал сам принцип. А то что каждый пункт можно реализовать по-разному очевидно.

 Кстати, на практике придется еще и задать приоритет направлений в третьем пункте. Например, если объект занимает всю длину или высоту (как нижний объект на последних картинках), то двигать его надо к левой границе или к правой границе или ставить по центру. Это правило должно быть задано априори.

ИМХО самое сложное все-таки минимизируемая функция.