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

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

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

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

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

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


Это сообщение отредактировал(а) 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