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

[overcoder]

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

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

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

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

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

Такое же как и первое, но более сложное.

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

[Dale]

overcoder, похоже, для просмотра картинок требуется регистрация на http://ipicture.ru . По крайней мере, мне ничего не удается увидеть по этим ссылкам.

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

[overcoder]

Dale, странно, я вроде проверял после отправки, выводило. Сейчас картинки на месте. Последовательность - картинкаи ПОД ней подпись.
RXL, большое спасибо!

[RXL]

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

[overcoder]

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

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

[Dale]

Для начала давайте уточним задачу. Первоочередной вопрос: как определить, что приемлемое решение найдено (я говорю "приемлемое", потому что, похоже, оно не единственное)? Без этого все остальные действия теряют смысл.

[overcoder]

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

Добавлено через 23 минуты и 48 секунд:
Вот к примеру в данном случае

при выравнивании хотелось бы получить это

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

[RXL]

А какова практическая сторона вопроса? Зачем все это нужно?

Добавлено через 1 минуту и 18 секунд:
overcoder, я бы попросил все таки присоединять изображения к посту, а не пользоваться помойками типа радикала, где срок жизни файла весьма ограничен!

[overcoder]

Да да, конечно, прошу прощения, подотрите 2 дубляжа пожалуйста.
>> А какова практическая сторона вопроса? Зачем все это нужно?
Разработка программного продукта для дизайнеров.

[npak]

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

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

помимо выравнивания вы ещё делаете кластеризацию - объединяете блоки в группы.  В качестве функции "плохости" кластеризации можно взять какую-нибудь метрику на плоскости - например, среднее расстояние между осевыми линиями блоков.

После того, как определитесь с мерой можно приступать к оптимизации. Различных методов - море.

[Dale]

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

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

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

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

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

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

б) элементы будут выровнены по линиям

Выравнивание по линии - тоже не проблема.

в) общая картина будет гармоничной (сложно сформулировать четче).

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

[Sla]

ух... аж ёкнуло...
Когда-то, очень давно решал аналогичную задачу.

Практическое применение? Будем считать оптимальный раскрой материала.

Если "верстать вручную, то исключительно блоками. Соответственно и алгоритм нужно подгонять.
Выделить блоки.
Группировка.
выравнивание по группам.




Добавлено через 3 минуты:
Нужно построить граф блоков

Учитывая что максимальный блок (ширина или высота <= группы.

А дальше... Рекурсивный алгоритм.

[Dale]

И еще:

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

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

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

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

[overcoder]

npak,  у меня эта идея уже давно витала в голове, спасибо за то, что придали ей некую форму!
Dale, вот в этом наверное и есть проблема - когда необходимо остановиться. Я полностью с вами согласен в том, что необходимо формализировать условие остановки, причем именно программным путем. Связка ПК-оператор отпадает, т.к. заказчик грубо говоря хочет получить на выходе magic button, которая сделает все сама.
Sla, практическое применение - облегчение работы дизайнера при создании презентаций. А какая задача была у вас?

[Dimka]

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

По-моему лучше в обратном порядке.

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

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

Это можно комбинировать - подвешивая к зонам "притяжения" "пружины".

[Sla]

Задача? Оптимальное движение ножей при раскрое материала (бумаги).
P - paper
Что-то наподобие

K1 - knife1
....

Kn left left left .... down
Kn-1 left left ... down
P - shift shift....
Kn up right ... down
....

потом это вылилось в студенческий НИР, получена премия аж!!! в 100 советских рублей.
Опубликована статья, и... даже оформлено изобретение (скромно, так, ковыряя носком землю )

[overcoder]

Dimka, просто супер! Постараюсь развить и обдумать за ночь. Может что то еще подскажете?
Sla, как я понимаю, это что то из области ЧПУ?
RXL, я хочу залить картинку 1'500*19'000, 6 мегабайт, как лучше поступить?

[Dale]

Dale, вот в этом наверное и есть проблема - когда необходимо остановиться. Я полностью с вами согласен в том, что необходимо формализировать условие остановки, причем именно программным путем. Связка ПК-оператор отпадает, т.к. заказчик грубо говоря хочет получить на выходе magic button, которая сделает все сама.

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

Давайте сделаем так. Попробуйте привести примеры "хороших" и "плохих" версток с указанием экспертной оценки их "хорошести", скажем, по n-балльной шкале и причин, по которым была поставлена именно такая оценка. А мы коллективным разумом попытаемся найти способ поверить гармонию алгеброй.

[overcoder]

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

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

Давайте сделаем так. Попробуйте привести примеры "хороших" и "плохих" версток с указанием экспертной оценки их "хорошести", скажем, по n-балльной шкале и причин, по которым была поставлена именно такая оценка. А мы коллективным разумом попытаемся найти способ поверить гармонию алгеброй.

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

[Dale]

Заливайте прямо сюда. На форме предварительного просмотра/редактирования сообщения есть опция для прикрепления файла к посту.

[Sla]

Бумагорезательный станок.
Вводились размеры листов. Идет непрерывный лист, вот его и нужно было резать.
В случае ЧПУ - алгоритм, практически, составляется до работы станка. В данном случае - размеры листов - произвольные  (условно)
Если смотреть на твои первые рисунки. Т.е. заранее известны размеры меньших листов, но известно, что в сумме они не больше Большего.

Вот как поступить в таком варианте

[overcoder]

Максимальный размер вложения: 1024 Кб, Максимум вложений на одно сообщение: 15
у меня в среднем от 4 мегабайт уже в 75% качестве jpeg

[Sla]

Вот ты привел в пример рисунки (первый пост) Я отталкиваюсь только пока от него.

Ты ведь как-то это все сделал?

Давай рассмотрим твои действия.
Ты определи блоки. Сгруппировал. Выровнял.
Опять сгруппировал. Выровнял.
И т.д.

Основная задача - определить блоки.

1. Найти максимальный блок вокруг которого все будет танцевать.

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


Добавлено через 46 секунд:
overcoder, а что ты хочешь выложить?

[Dale]

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

Попробуйте покомпактнее. Вот как у Sla - пара килобайт, и при этом идея отлично видна.

[overcoder]

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

[Dale]

Я скорее хотел бы увидеть набор схем с комментариями.

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

Без ненужных деталей, которые только загромождают картину.

[overcoder]

У меня там вертикальные ленты принтскринов
(пс_1) - (схема_1)
(пс_2) - (схема_2)
................................
(пс_25) - (схема_25)

в среднем 15-30 кадров
есть несколько на 50 и парочка на 80 кадров

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

[Dale]

Вот в первом посте картинки близки к идеалу. И выразительны, и размерчик - самое то, единицы килобайт.

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

[overcoder]

я работаю над этим



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

Вот в первом посте картинки близки к идеалу. И выразительны, и размерчик - самое то, единицы килобайт.

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

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

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

[RXL]

RXL, я хочу залить картинку 1'500*19'000, 6 мегабайт, как лучше поступить?

Такие размеры не для общения - не все сидят на толстых каналах!
Варианты решения:
1. Уменьшить до разумных (и разрешенных форумом) 1024х1024.
2. Уменьшить и поместить в архив (чтобы не распознавалось форумом как картинка) - размер до 1 МБ.

С манией гигантизма надо бороться! Почитайте мемуары изобретателя LSD: если бы он делал опыты с веществами в таком количестве, то разорил бы фирму.