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

[overcoder]

Просмотрев все я выбрал наиболее сложные, вот одна из них (приводилась в первом посте, теперь с комментариями)

Подобными будем считать фигуры, лежщие на одной строке, или на одном столбце, с небольшим допуском отклонения.
В данном случае полностью (по высоте и ширине) подобными будут фигуры [1,3], [4,7], [6,8].
Выравнивание должно происходить по левому краю у [4,7], [6,8]
по верхнему краю [1,2,3], [4,6], [7,8]
По вертикальной центральной линии [1,4,7], [3,6,8], [2,5,9]
Внутри фигуры 5 находятся 11, 12, 13, 14, для них происходит выравнивание по вертикальной центральной линии, но они не учавствуют в других действиях "вне" фигуры 5, т.е. [4,6] выравнивается без учета 11.

В верхнем левом углу находится слайд, который подается на вход. Справа от него схема, которая содержит прямоугольники с координатами (т.к. в объектной модели MS PP любой объект представляет собой прямоугольник, характеризующийся координатами X,Y, высотой и шириной).
Внизу слева находится тоже самое, только в более наглядной форме, перерисованное вручную. Внизу справа - конечный вид, когда выполнились преобразования. Черные линии проведены для наглядности между какими фигурами происходило выравнивание.

Одна из многих возникающих проблем - имеем ситуацию как на картинке

Видно, что согласно принятым условиям, все 4 фигуры будут подобными, так как отличия в X Y W(idth) и H(eight) довольно малы.
В какой очередности вы бы производили подгон их размеров?

[Sla]

Упрощай задачу.
начинай от простейшего.

Расположи вот это, придумай алгоритм
Увеличивай количество, изменяй размеры.

[overcoder]

Sla, это пройденный этап, с этого можно сказать начиналось.

[Sla]

1. определяем максимальную ширину и максимальную высоту столбца и колонки
2. выравнивание по верху
3. выравнивание по левому краю (взять за как отправную точку)
4. выровняли по правому максимальному
4. выравнивание по максимальной ширине и высоте.

что получаем
выровняли по верху 1, 2
выровняли по левому 1, 3
берем 2-й и тянем вправо до упора (макс ширина)
берем 4-й - тянем до упора вправо
Остался не выровненный низ.
Тянем 4-й или 2-ой ( в зависимости от размеров - в примере - 4-ый) до упора вниз

[Dimka]

Offtopic:

О дизайне: от такого оранжевого фона и падучая может приключиться.

Поставлю в угол.

[overcoder]

Sla, несомненно так, но это конкретно для этого случая, а ведь их бесконечно много комбинаций... Нужно нечто общее, т.е. в большей степени не пошаговость "1 туда, 2 сюда", а принципы, наподобие "выделяем группы подобных объектов", "приводим размеры внутри групп", "разбираем коллизии". А в идеале всё это увязать в один общий алг.
Я, наверное, немного не так выразился, сказав "В какой очередности вы бы производили подгон их размеров?". Мне хотелось показать что в этой ситуации нельзя обрабатывать их пошагово (хотя может и можно, но врядли), а надо как-то целиком их засечь и усреднить (назовем это так)
Dimka, оранжевые - это зоны на мастер-слайде (о них речь не идет), стояла задача сделать их максимально яркими и заметными, из двух зол (вторым был ядовито-зеленый) выбрал наименьшее
Мне очень понравилась идея с пружинами, предложенная вами, но пока я не вижу как "прикрутить" ее сюда.
Но в любом случае она заслуживает внимания.

[Sla]

Вот здесь ты и делаешь ошибку, на мой взгляд.

У тебя есть объект прямоугольник
Есть объект лист
У прямоугольника есть метод перемещение и свойства (размеры)
У листа есть ограничения размера и требования на размещение прямоугольников. Лист должен быть больше любого прямоугольника.

В любом случае должны быть какие шаги.
!. Инициализация
2. Определение групп
3. Перемещение групп.

Причем заметь - группа - по сути - наследник от листа.

Так что без "шагов" никак нельзя.

Вот почему я и сказал что -  "от простейшего"

[overcoder]

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

[Dale]

Одна из многих возникающих проблем - имеем ситуацию как на картинке
...
Видно, что согласно принятым условиям, все 4 фигуры будут подобными, так как отличия в X Y W(idth) и H(eight) довольно малы.
В какой очередности вы бы производили подгон их размеров?

Мы имеем право уменьшать прямоугольники?

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

[overcoder]

Да, имеем, желательно пропорционально или непропорционально в небольших пределах
Например 100*47 мы можем сделать 100*50, но вот 100*25 станет 200*50

[Dale]

Рискую показаться назойливым, но все же повторюсь.

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

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

[Sla]

Вот показательный пример

Что у тебя, и что у меня...

Что правильней?

[Dale]

Что правильней?

И второй вопрос: почему?

[Sla]

Рискую показаться назойливым, но все же повторюсь.

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

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

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

Надо создать объектную модель задачи. Определить, что первично - прямоугольник или лист.

Подгонка размеров? - это мелочи, только метод.

[overcoder]

Вот! Вы стали лучше понимать суть проблемы - в первую очередб что НУЖНО, а затем - как этого достичь.
Sla, нельзя сказать у кого правильнее, т.к. нет критерия этой правильности.
Dale, тоже верно, мы не можем сказать где проблемные области потому что если подравнивать относительно друг друга то картина будет "плавающей", и эти проблемные области могу появляться и исчезать в нескольких местах сразу при движении всего одного элемента...

[Dale]

вот тут как раз и есть "тайный" смысл. Вот эти подгонки и перемещения должны настодоесть до чЁртиков, так чтоб понять "А что же нам собственно нужно"
...
Подгонка размеров? - это мелочи, только метод.

Совершенно верно. Я именно поэтому и предлагал такой подход: берем начальную конфигурацию, оцениваем, находим проблемную область, вручную двигаем/масштабируем, убеждаемся, что стало получше; находим очередную проблемную область... и так далее, пока проблем не останется.

Но:

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

А на нет, как известно, и суда нет...

[overcoder]

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

Ну на вскидку можно для подгонки сходных размеров взять отношение в первоначальной картине подобных но не равных к отношению после обработки - если уменьшилось, значит хорошо, двигаемся в верном направлении.
Для подравнивания то же самое, только по сторонам - количество объектов не лежщих на одной прямой (по top, left, bottom, right, center или middle) к количеству лежащих, уже после каких либо действий.
В приложениях несколько кошмарчиков

[Sla]

Dale, чувствуется -одна школа

[Dale]

Dale, чувствуется -одна школа

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

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

[overcoder]

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

А на нет, как известно, и суда нет...

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

Offtopic:

Фактически, звучит как
- У меня есть задача, но нет хода решения.
- Предоставьте ход решения.
- Не могу, у меня его нет.
- На нет и суда нет.

Наверное мы немного запутались...
Вот, кстати, для ясности по ОМ MS PP:

[Dale]

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

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

Для меня сейчас главное - стратегия: "сначала я сдвигаю прямоугольник X вверх, чтобы выровнять его верхний край по прямоугольнику Y", или: "прямоугольники N1, N2, ... N5 расположены в одном ряду, поэтому я так распределяю их вдоль ряда, чтобы интервалы между ними стали одинаковы", и т.д.

Отсюда я могу сделать такие выводы: если у соседних прямоугольников верхний края на разной высоте - это плохо; если интервалы между прямоугольниками в одном ряду разные - это плохо; и т.д.

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

Ну а теперь я могу точно сказать: чем больше значение штрафа для данного прямоугольника, тем хуже он размещен. Как минимизировать этот штраф - отдельная задача.

Именно отсюда просьба: решите на наших глазах несколько подобных простых задач вручную, по шагам, комментируя каждый раз, что именно в данный момент не нравится и почему делается именно такой шаг. Это вовсе не алгоритм, до алгоритма нам еще как до Пекина по-пластунски. Сейчас нужно получить хотя бы первое приближение для штрафной функции. Потом можно будет ее уточнять по ходу, когда обнаружатся слабые стороны (сразу всего все равно не предусмотреть).

Индукция - от частного к общему...

Offtopic:

Фактически, звучит как
- У меня есть задача, но нет хода решения.
- Предоставьте ход решения.
- Не могу, у меня его нет.
- На нет и суда нет.

Наверное мы немного запутались...

Отнюдь. Звучит это совершенно иначе:
- Хочу, чтобы компьютер сделал мне красиво.
- Хорошо. Покажите нам примеры, как из "некрасиво" делается "красиво", и поясните, почему именно решили, что сначала было некрасиво, а теперь стало куда лучше.
- А не буду.

Как-то так...

[Sla]

хм, я вот подумал... Это похоже все на рендеринг html блочной верстки
за исключением центровки по горизонтали.

Я тут по быссссраму нарисовал
http://slasoft.kharkov.ua/test/rectandle.html


"Штрафные санкции" - свойство margin (margin-top, margin-bottom, margin-left, margin-right)

 Надо заметить, что "штрафные санкции" могут помочь, но это пока отдельный разговор.

[Dale]

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

В описанном примере раскроя штраф более очевиден - количество отходов. Если есть два варианта раскроя, лучшим будет тот, который дает меньше обрезков.

В данной задаче критерии более расплывчаты, со смещением от прагматики в эстетику. Значит, сперва придется разобраться, что именно наиболее оскорбляет наше чувство прекрасного: невыровненность блоков по горизонтали/вертикали, разброс их размеров, неодинаковость зазоров по бокам и т.д. Разберемся с этим - дальше будет проще: научимся оценивать эти критерии количественно, а потом поищем алгоритмы их оптимизации.

[Sla]

Честно, я так и не понял конечную задачу.
Для чего?

Для типографики?
Для раскроя?
Разные критерии штрафов.

[Dimka]

Ну, собственно, система штрафов и их минимизации - это те же "пружины", только в профиль

Sla, читай выше - для оформления слайдов презентации.

[Dale]

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

Когда мы компонуем эти прямоугольники в виде диаграммы, у нас совершенно другая функция штрафов, которая отражает отклонение текущей компоновки от некоей идеальной. Но принцип тот же - чем штраф меньше, тем компоновка лучше.

Основное назначение функции штрафа - дать возможность объективно сравнивать две конфигурации между собой. Без этого мы не сможем сказать, какой раскрой или диаграмма лучше. А значит, не имеем возможности оценить, движемся ли мы в сторону улучшения или наоборот.

И конечной эту задачу назвать трудно. Оценить штраф - не самоцель, а лишь средство определить направление к цели. Факт, что конфигурация A имеет штраф 357, практически ничего нам не говорит. А вот если мы переместим прямоугольник X на сантиметр правее и получим конфигурацию B со штрафом 164, то это уже показатель, что новая конфигурация лучше прежней.

Опять же скользкий вопрос - когда остановить оптимизацию? Имея штрафную функцию, мы можем дать определенный ответ: когда штраф будет ниже такого-то порога. (Примерно то же имеем для раскроя: останавливаемся, когда отходы станут меньше какого-то приемлемого уровня - лучше иметь хорошее решение сейчас, чем идеальное в далеком будущем).

[overcoder]

Dale, примите мои извинения, я вас не так понял, сейчас организую пошаговые элементарные примеры
Sla, дизайнеры сделали презентацию, но т.к. спешили или были не очень аккуратны она выглядит неряшливо. Задача - написать надстройку для MS PP (одна большая кнопка, возможно несколько изменяемых параметров для настройки), при работе которой каждый слайд презентации анализировался и т.с. становился лучше чем был (подравнивание, размеры и все, о чем говорилось выше).
В перспективе - дизайнеры просто накидывают элементы на слайд примерно в нужные места, нажимают кнопку и получают готовый оформленный слайд.
Dimka, где можно почитать про ваши "пружины" используемые в GUI, что бы вас не утруждать более подробным пересказом их свойств и возможностей? Я думал над ними, они почти идеально подходят для другой второстепенной задачи - т.н. партнерских или спонсорских досок (2 картинки в приложениях)

[Dale]

Ну, собственно, система штрафов и их минимизации - это те же "пружины", только в профиль

Не совсем.

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

[Sla]

Dimka предложил великолепное решение.

1. Равномерное размещение по вертикали
Каждый Прямоугольник подвешивается на пружине.
Каждая пружина имеет свой коэффициент растяжения
Управляя этими коэффициентами можно достичь любое приемлемое расположение.

2. Для горизонтального - поворачиваем схему.

Добавлено через 2 минуты и 1 секунду:

Ну, собственно, система штрафов и их минимизации - это те же "пружины", только в профиль

Не совсем.

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

Параметры переходных процессов можно учесть.

[Dale]

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