Прямоугольники на плоскости

	Комментарий модератора
	Объединил аттачи и текст сообщения во втором посте

0

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

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

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

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

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

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

0

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

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

0

Основные правила:
1) не создавать коллизий (ситуаций, когда 1 фигура лежит поверх другой, даже частично)
2) размеры желательно оставлять в предлах 5-10% от первоначальных в обе стороны (+ и -)
3) взаимное расположение тоже не должно меняться
4) при изменении одной из сторо фигуры больше чем на 5% менять пропорционально и другую сторону
Главные задачи:
1) избавиться от существующих коллизий
2) привести размеры подобных элементов (например, несколько прямоугольников в строке с размерами 100*20, 100*22, 98*21 должны стать одинаковыми по 100*21 примерно, если испольовать усреднение)
3) выровнять элементы по сторонам (top, left, bottom, right, middle, center) - как это отображено в примерах.

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

0

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

0