Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: 1 2 3 [Все]   Вниз
  Печать  
Автор Тема: Прямоугольники на плоскости  (Прочитано 104320 раз)
0 Пользователей и 1 Гость смотрят эту тему.
overcoder
Участник

ua
Offline Offline

« : 11-01-2011 14:35 » 

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


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


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


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


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


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

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

* 1.png (6.08 Кб - загружено 4558 раз.)
* 2.png (6.23 Кб - загружено 3823 раз.)
* 3.png (5.64 Кб - загружено 4011 раз.)
* 4.png (8.2 Кб - загружено 3984 раз.)
* 5.png (7.7 Кб - загружено 4174 раз.)
« Последнее редактирование: 11-01-2011 17:55 от RXL » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #1 : 11-01-2011 14:50 » 

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #2 : 11-01-2011 17:52 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #3 : 11-01-2011 17:54 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
overcoder
Участник

ua
Offline Offline

« Ответ #4 : 11-01-2011 18:23 » 

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

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #5 : 11-01-2011 19:03 » 

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #6 : 11-01-2011 19:12 » 

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

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



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



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

* 10.png (6.35 Кб - загружено 3882 раз.)
* Б1.png (6.39 Кб - загружено 3839 раз.)
« Последнее редактирование: 11-01-2011 23:07 от overcoder » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 11-01-2011 19:36 » 

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

Добавлено через 1 минуту и 18 секунд:
overcoder, я бы попросил все таки присоединять изображения к посту, а не пользоваться помойками типа радикала, где срок жизни файла весьма ограничен!
« Последнее редактирование: 11-01-2011 19:38 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
overcoder
Участник

ua
Offline Offline

« Ответ #8 : 11-01-2011 19:42 » 

Да да, конечно, прошу прощения, подотрите 2 дубляжа пожалуйста.
>> А какова практическая сторона вопроса? Зачем все это нужно?
Разработка программного продукта для дизайнеров.
« Последнее редактирование: 11-01-2011 23:08 от overcoder » Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #9 : 11-01-2011 19:59 » 

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

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

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #10 : 11-01-2011 20:36 » 

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

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

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

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


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

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

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

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #11 : 11-01-2011 21:00 » 

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

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

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




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

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

А дальше... Рекурсивный алгоритм.
« Последнее редактирование: 11-01-2011 21:03 от Sla » Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #12 : 11-01-2011 21:04 » 

И еще:

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

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #13 : 11-01-2011 21:10 » 

npak,  у меня эта идея уже давно витала в голове, спасибо за то, что придали ей некую форму!
Dale, вот в этом наверное и есть проблема - когда необходимо остановиться. Я полностью с вами согласен в том, что необходимо формализировать условие остановки, причем именно программным путем. Связка ПК-оператор отпадает, т.к. заказчик грубо говоря хочет получить на выходе magic button, которая сделает все сама.
Sla, практическое применение - облегчение работы дизайнера при создании презентаций. А какая задача была у вас?
« Последнее редактирование: 11-01-2011 21:13 от overcoder » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 11-01-2011 21:23 » 

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

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

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 11-01-2011 21:30 » 

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

K1 - knife1
....

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #16 : 11-01-2011 21:40 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 11-01-2011 21:45 » 

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #18 : 11-01-2011 21:50 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #19 : 11-01-2011 21:52 » 

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #20 : 11-01-2011 21:53 » 

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

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


* ex.jpg (2.56 Кб - загружено 3788 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #21 : 11-01-2011 21:54 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #22 : 11-01-2011 22:00 » 

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

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

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

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

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

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


Добавлено через 46 секунд:
overcoder, а что ты хочешь выложить?
« Последнее редактирование: 11-01-2011 22:01 от Sla » Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #23 : 11-01-2011 22:01 » 

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #24 : 11-01-2011 22:22 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #25 : 11-01-2011 22:53 » 

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #26 : 11-01-2011 23:27 » 

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

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

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #27 : 11-01-2011 23:36 » 

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

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

Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #28 : 11-01-2011 23:46 » 

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



Добавлено через 1 минуту и 8 секунд:
Вот в первом посте картинки близки к идеалу. И выразительны, и размерчик - самое то, единицы килобайт.
в первом посте картинки создавались "от балды" вручную, и отражают общие принципы, т.е. в какой то степени идеализированны.
Таких бы схем - да побольше, с комментариями для каждого случая, что в них хорошо и что плохо. А если будет последовательность кадров, на которой показано превращение диаграммы из никудышней в образцовую - так и вовсе здорово.
перерисовывать для каждого случая нереально, я только принтскрины делал несколько часов (используя SnagIt для ускорения процесса).
Последовательности превращения диаграммы не будет в любом случае, т.к. это предполагает использование алгоритма, поиск которого является искомой задачей.  Здесь была моя ладья...
А вот подробные комментарии обязательно будут присутствовать.
« Последнее редактирование: 11-01-2011 23:49 от overcoder » Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #29 : 12-01-2011 05:01 » 

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

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

С манией гигантизма надо бороться! Почитайте мемуары изобретателя LSD: если бы он делал опыты с веществами в таком количестве, то разорил бы фирму.
« Последнее редактирование: 12-01-2011 05:06 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
overcoder
Участник

ua
Offline Offline

« Ответ #30 : 12-01-2011 17:59 » 

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



Подобными будем считать фигуры, лежщие на одной строке, или на одном столбце, с небольшим допуском отклонения.
В данном случае полностью (по высоте и ширине) подобными будут фигуры [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) довольно малы.
В какой очередности вы бы производили подгон их размеров?

* 1s.png (58.16 Кб - загружено 2979 раз.)
* 1.png (113.69 Кб - загружено 2771 раз.)
* 3.png (7.49 Кб - загружено 2681 раз.)
« Последнее редактирование: 12-01-2011 18:12 от overcoder » Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #31 : 12-01-2011 18:13 » 

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


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

* exa.jpg (9.07 Кб - загружено 2907 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #32 : 12-01-2011 18:19 » 

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

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #33 : 12-01-2011 18:36 » 

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

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




Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #34 : 12-01-2011 19:29 » 

Offtopic:

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
overcoder
Участник

ua
Offline Offline

« Ответ #35 : 12-01-2011 19:42 » 

Sla, несомненно так, но это конкретно для этого случая, а ведь их бесконечно много комбинаций... Нужно нечто общее, т.е. в большей степени не пошаговость "1 туда, 2 сюда", а принципы, наподобие "выделяем группы подобных объектов", "приводим размеры внутри групп", "разбираем коллизии". А в идеале всё это увязать в один общий алг.
Я, наверное, немного не так выразился, сказав "В какой очередности вы бы производили подгон их размеров?". Мне хотелось показать что в этой ситуации нельзя обрабатывать их пошагово (хотя может и можно, но врядли), а надо как-то целиком их засечь и усреднить (назовем это так)
Dimka, оранжевые - это зоны на мастер-слайде (о них речь не идет), стояла задача сделать их максимально яркими и заметными, из двух зол (вторым был ядовито-зеленый) выбрал наименьшее Улыбаюсь
Мне очень понравилась идея с пружинами, предложенная вами, но пока я не вижу как "прикрутить" ее сюда.
Но в любом случае она заслуживает внимания.
« Последнее редактирование: 12-01-2011 19:44 от overcoder » Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #36 : 12-01-2011 19:55 » 

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

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

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

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

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #37 : 12-01-2011 19:59 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #38 : 12-01-2011 20:45 » 

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #39 : 12-01-2011 21:00 » 

Да, имеем, желательно пропорционально или непропорционально в небольших пределах
Например 100*47 мы можем сделать 100*50, но вот 100*25 станет 200*50
Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #40 : 12-01-2011 21:04 » 

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #41 : 12-01-2011 21:07 » 

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

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



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

* exe1.jpg (10.84 Кб - загружено 2862 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #42 : 12-01-2011 21:11 » 

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

И второй вопрос: почему?
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #43 : 12-01-2011 21:14 » 

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

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

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

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

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #44 : 12-01-2011 21:24 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #45 : 12-01-2011 21:26 » 

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

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

Но:

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #46 : 12-01-2011 21:39 » 

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

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

* u1.png (61.29 Кб - загружено 1052 раз.)
* u2.png (67.76 Кб - загружено 1081 раз.)
* u3.png (55.23 Кб - загружено 1064 раз.)
Записан
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #47 : 12-01-2011 21:43 » 

Dale, чувствуется -одна школа Улыбаюсь
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #48 : 12-01-2011 21:55 » 

Dale, чувствуется -одна школа Улыбаюсь

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #49 : 12-01-2011 22:00 » 

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

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

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

* размеры.png (10.7 Кб - загружено 2716 раз.)
« Последнее редактирование: 12-01-2011 22:02 от overcoder » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #50 : 12-01-2011 23:24 » 

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

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

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

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

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

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

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

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

Offtopic:

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

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

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

Как-то так...
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #51 : 13-01-2011 08:52 » 

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

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


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

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



Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #52 : 13-01-2011 09:16 » 

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #53 : 13-01-2011 09:33 » 

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

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

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #54 : 13-01-2011 10:08 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #55 : 13-01-2011 10:22 » 

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

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

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

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

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
overcoder
Участник

ua
Offline Offline

« Ответ #56 : 13-01-2011 10:23 » 

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

* sponsor.jpg (92.4 Кб - загружено 1075 раз.)
* sponsor2.jpg (98.5 Кб - загружено 1025 раз.)
« Последнее редактирование: 13-01-2011 10:25 от overcoder » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #57 : 13-01-2011 10:29 » 

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

Не совсем.

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #58 : 13-01-2011 11:25 » 

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

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

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

Добавлено через 2 минуты и 1 секунду:
Ну, собственно, система штрафов и их минимизации - это те же "пружины", только в профиль Улыбаюсь

Не совсем.

Штраф - статическая характеристика для данной конфигурации. Если модель пружины будет более-менее похожа на реальную пружину, мы получаем динамическую систему: потянули за один прямоугольник - вся картина пришла в движение. А при некотором невезении можно и вовсе колебательную систему получить, которая будет долго раскачиваться, а то и генерировать начнет.
Параметры переходных процессов можно учесть.
« Последнее редактирование: 13-01-2011 11:27 от Sla » Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #59 : 13-01-2011 11:34 » 

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

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #60 : 13-01-2011 12:09 » 

Вот примерный рисунок



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

Здесь нужно играться и играться до просветления

* exe1.jpg (12.26 Кб - загружено 2542 раз.)
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #61 : 13-01-2011 12:20 » 

Sla, насколько я понял, в этой модели каждый блок имеет известный вес и подвешен на пружине известной жесткости, что позволяет однозначно определить его координату в состоянии равновесия?
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #62 : 13-01-2011 12:36 » 

весом является размер блока (площадь).

Возможны варианты, что площади одинаковые (вес), но ширина больше - выбирается ближайшая точка подвешивания.

Я и говорю - до просветления.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #63 : 13-01-2011 12:49 » 

Вот, попытался отобразить элементарный случай.
*привоис = приводим

* анимация.gif (43.57 Кб - загружено 1186 раз.)
« Последнее редактирование: 13-01-2011 12:52 от overcoder » Записан
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #64 : 13-01-2011 12:54 » 

весом является размер блока (площадь).

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

И еще такой момент. Зная вес блока и упругость пружины, мы без труда найдем его координату. Вес (площадь) найти легко. Но вот как подобрать упругость, чтобы все выглядело эстетично, - большой вопрос.

Добавлено через 9 минут и 6 секунд:
Вот, попытался отобразить элементарный случай.

Просто изумительно. Теперь можно попробовать произвести оценку "неидеальности" по приведенным в комментариях критериям.
« Последнее редактирование: 13-01-2011 13:03 от Dale » Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #65 : 13-01-2011 13:07 » 

Цитата
Тогда автоматически получается, что при прочих равных условиях бОльшие блоки провисают ниже. Действительно ли такой эффект желателен?
можно играть коэффициентами жесткости.
Например, смотрим на рисунок.
Все что подвешено к верху - висит на нерастяжимой пружине = выравнивание поверху
Широкий блок перекрывает два верхних - подвешиваем на нерастяжимую пружину, но делаем "базой"

нижние блоки вешаем на нерастяжимые относительно базы.

Я не показал момента, когда блоки находятся один под одним.

Сейчас рассматривается только метод.


Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #66 : 13-01-2011 13:17 » 

С пружинами еще вот какая неприятность может возникнуть.

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

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

А решать систему уравнений движения для N тел, связанных пружинами, в вязкой среде для данной задачи несколько хардкорно, IMHO.
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #67 : 13-01-2011 13:44 » 

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

Определение максимальной высоты ЛИСТА.
Определение максимальной ширины ЛИСТА.
Учитываем что шаг поиска фиксирован, и немного меньше минимальной высоты/ширины.
Этот шаг может быть и минимальным расстоянием между блоками.

Я понимаю, что, наверное, эти задачи стояли перед ТС, но хотелось бы их услышать.
Он все напрягает нас на выдачу готового алгоритма Улыбаюсь


зы. (на память)
Кто-то расставляет изначально блоки? Или эти блоки уже размещены автоматически по какому-то оптимальному решению?
В случае "спонсорских" досок Добавление - в очередь. Ушел блок - произвольное покидание очереди.
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
overcoder
Участник

ua
Offline Offline

« Ответ #68 : 13-01-2011 16:39 » 

Просто изумительно. Теперь можно попробовать произвести оценку "неидеальности" по приведенным в комментариях критериям.
Введем определения что бы не путаться.
Подобными считаем те, которы лежат в одной строке или одном столбце, имеют различия по высоте не более Х% от их средней высоты и отличия по ширине не более Y% от средней ширины. Есть три вида подобных элементов - у которых почти совпадает только ширина, почти совпадает только высота, почти совпадает ширина и высота (полностью подобные).
Положим, что
1) подобные элементы разного размера создают неидеальность. Отталкиваться будем от их количества.
Допустим в ряд лежат 3 квадрата со сторонами 100, 99, 101. Они будут полностю подобны между собой, но т.к. все три разные, то "идеальность" будет 0 из 3 (общее количество фигур)
2) элементы, лежащие на полосе в предлах +- Z% от величины (w или h) фигуры должны находится с ней на одной линии. Если одни лежат в этой полосе, но не на одной линии то они тоже создают неидеальность.
можно играть коэффициентами жесткости.
С пружинами все не однозначно потому как они позволяют равномерно распределить блоки , но никак не помогут с выравниванием относительно друг друга.

Пружины 1 и 3 будут расятнуты одинаково, а пружина 2 будет растянута больше, что сместит блок 5 ниже блока 4 и никак не поможет в решении.
Их можно использовать для равномерного распределения множества разных блоков по площади, а не в данном случае.
С пружинами еще вот какая неприятность может возникнуть.
Груз на пружине - это маятник. Толкнешь его - он начнет раскачиваться.
Ясное дело что никто не будет это моделировать, т.к. это излишне. От свойств пружины нам "нужно" только то, что у нее есть длинна, устойчивое положение (УП), положение сжатия (меньше УП), когда она расталкивает блоки на своих концах и положение растягивания, когда она стягивает блоки на концах (больше УП).
Я понимаю, что, наверное, эти задачи стояли перед ТС, но хотелось бы их услышать.
Кто-то расставляет изначально блоки? Или эти блоки уже размещены автоматически по какому-то оптимальному решению?
Он все напрягает нас на выдачу готового алгоритма Улыбаюсь
Я не напрягаю вас на выдачу готового алга, а обращаюсь за советом и помощью, т.к. длительное время проведенное над этой задачей, дало только общие принципы что надо ровнять и приводить подобные, но задача до сих пор не решена.
Задача сформулирована (дословно) "подровнять и красивенько расположить блоки которые стоят криво или залазят друг на друга".
Изначально эти блоки располагают преимущественно девушки от 20 до 30 лет вообще не задумываясь что в PowerPoint есть встроенные удобные функции подравнивания выделенных элементов по всем мыслимым сторонам, распределения по поверхности и прочее.
По поводу досок спонсоров - давайте не будем их трогать, это не основная задача, но именно в ней надо использовать пружины в том виде как они были предложены.

* пруж1.png (11.02 Кб - загружено 2592 раз.)
« Последнее редактирование: 13-01-2011 16:44 от overcoder » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #69 : 13-01-2011 17:48 » 

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

Думаю, с 1D случаем справиться будет легче. По крайней мере полученное таким образом решение будет некой основой, которую можно попробовать улучшать. Решать сразу 2D случай - сложнее и мозгов участвующих может не хватить.

Добавлено через 2 часа, 13 минут и 2 секунды:
Пусть у нас страница выглядит примерно так: вертикальное размещение приемлемое, горизонтальное - нет. Будем считать, что каждый блок имеет вес 1 (если хочется, весом можно взять высоту блока). Тогда проекция блоков по горизонтали создаёт ступенчатую "функцию" от ширины листа. Все вертикальные границы блоков как бы продлены на всю высоту листа.



Это можно кодировать массивом точек, что наглядно, но требует много данных:
(0, 0, 1, 2, 2, 1, 1, 0, 1, 1, 1, 1, 0)

Либо (что актуально для больших страниц, имеющих метрические размеры), её можно кодировать массивом структур вида (уровень, длина):
((0, 2), (1, 1), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)). Это менее наглядно, зато удобнее для алгоритмической обработки.

Предположим, что нормальным расстоянием между краями блоков является 2 и более. Тогда во втором представлении элементарно находятся проблемные места: (+, (1, 1), +, +, (0, 1), +, (0, 1)). Если расстояние меньше допустимого, значит в этом проблемном месте нужно "склеить" или "растолкать" границы блоков. Делать это в каждом случае можно двумя способами: либо уменьшить длину левого хорошего участка и увеличить длину текущего плохого на нужную величину, либо уменьшить длину правого плохого участка и увеличить длину текущего плохого на нужную величину. Каждая такая перестановка может:
- превратить соседний хороший участок в участок 0-й длины - такой участок можно смело выкинуть, если его уровень 0, иначе это потребует ликвидации блоков, что неприемлемо;
- превратить соседний участок в плохой, оставив плохим текущий участок - если при этом суммарный дефицит длин участков уменьшился, это хорошее преобразование, иначе - плохое (вроде бы не должен уменьшаться дефицит);
- превратить соседний участок в плохой, сделав текущий участок хорошим (вроде бы это не даст уменьшения дефицита);
- сохранить соседний участок хорошим, сделав текущий участок тоже хорошим - однозначно положительное преобразование, устраняющее дефицит.

В рассматриваемом примере исходный дефицит длин составляет 3.

Возможные в данном случае варианты модификаций.
((0, 1), (1, 2), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
((0, 2), (1, 2), (2, 1), (1, 2), (0, 1), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
((0, 3), (1, 0), (2, 2), (1, 2), (0, 1), (1, 4), (0, 1)) - ликвидация блока, не принимается
((0, 2), (1, 1), (2, 2), (1, 1), (0, 2), (1, 4), (0, 1)) - дефицит 3, бесполезно, не принимается
((0, 2), (1, 1), (2, 2), (1, 2), (0, 2), (1, 3), (0, 1)) - дефицит 2, полезно, принимается
((0, 2), (1, 1), (2, 2), (1, 2), (0, 1), (1, 3), (0, 2)) - дефицит 2, полезно, принимается

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

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

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

В данном случае:
((0, 3), (1, 0), (2, 2), (1, 2), (0, 2), (1, 2), (0, 2)) - неприемлемо, так как увеличился блок меньшего уровня 0 за счёт блока большего уровня 1.
((0, 2), (1, 0), (2, 3), (1, 2), (0, 2), (1, 2), (0, 2)) - приемлемо, так как увеличился блок большего уровня 2 за счёт блока меньшего уровня 1. При этом дефицит стал 0.

Итак, найдено одно из возможных оптимальных решений:
((0, 2), (2, 3), (1, 2), (0, 2), (1, 2), (0, 2))
или
(0, 0, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0)


* pagemake.png (2.03 Кб - загружено 2880 раз.)
* pagemake1.png (2.05 Кб - загружено 2540 раз.)
« Последнее редактирование: 13-01-2011 20:01 от dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
overcoder
Участник

ua
Offline Offline

« Ответ #70 : 13-01-2011 20:53 » 

Возможно я чего то не понял, но как производить декодирование?
Если у нас будет в столбце лежать 4 блока, после расчета модификаций как мы поймем который из них изменять?
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #71 : 14-01-2011 09:08 » 

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

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

Сразу отвечу: "А может тебе ещё и ключ от квартиры дать, где деньги лежат?" (c) Остап Бендер

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #72 : 14-01-2011 09:59 » 

С пружинами еще вот какая неприятность может возникнуть.
Груз на пружине - это маятник. Толкнешь его - он начнет раскачиваться.
Ясное дело что никто не будет это моделировать, т.к. это излишне. От свойств пружины нам "нужно" только то, что у нее есть длинна, устойчивое положение (УП), положение сжатия (меньше УП), когда она расталкивает блоки на своих концах и положение растягивания, когда она стягивает блоки на концах (больше УП).

А вот не факт, что сумеете обойтись без такого моделирования.

Представьте себе, что у нас горизонтальная цепочка связанных пружинами блоков: 1-2-3-... Допустим, нам пришлось подвинуть блок 2 левее, чтобы выровнять его с вышележащим товарищем. Сделать это мы можем, сделав пружину 1-2 немного жестче.

Двигаясь влево, блок 2 сильнее натягивает пружину 2-3. Поскольку натяжение пружины 3-4 еще не менялось, блок 3 тоже едет влево, пока не придет в равновесие. Дальше по цепочке едут влево блоки 4 и т.д. до конца цепочки. Но это еще не все.

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

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

Как видите, никакого специального моделирования колебаний не потребуется. Пружинная модель сама по себе достаточно неустойчива.
« Последнее редактирование: 14-01-2011 10:01 от Dale » Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #73 : 14-01-2011 12:36 » 

Dale, колебания физической системы грузов на пружинах обусловлено, как мне кажется, наличием инертной (не тяжёлой) массы. Её вовсе необязательно тащить в модель. Без инертной массы, если силы сделать пропорциональными координате, а не её второй производной, если каждое дискретное движение каждого блока будет пропорционально разнице сил действующих на этот блок пружин, система без колебаний придёт в равновесие - это сходящийся процесс. Окончание этого процесса происходит при условии, что разница сил становится меньше минимального порога (погрешности). И это мною проверялось на практике - когда-то я писал AI для игры в "Сапёра" и таким методом балансировал вероятности закрытых клеток Улыбаюсь Поэтому и говорю, что пружины и штрафы - это очень похожие задачи.

В данном случае точность определяется либо пикселями (целыми числами, при диапазоне в 4 десятичных порядка), либо метрическими единицами, но даже в худшем случае вряд ли будет DPI большее 600 (для печати на принтере).
« Последнее редактирование: 14-01-2011 12:40 от Dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
overcoder
Участник

ua
Offline Offline

« Ответ #74 : 14-01-2011 12:42 » 

Dimka, у вас было очень подробное объяснение, и только этот момент вызвал вопрос. Теперь все понятно, спасибо за идею.
Решать за меня задачу конечно же не нужно, скажите только, можно ли где то прочитать про пружины которые вы впервые упомянули еще в 15-м ответе?
Dale, согласен с вами, но это уже зависит от того, как мы будем обрабатывать положения блоков и натяжения пружин. Если последовательно то действительно велика вероятность что система дестабилизируется и даже могут возникнуть незатухающие колебания. Другое дело если мы будем расчитывать положение каждого блока в определенный момент времени, затем сдвигать все, затем снова проводить оценку и так же введем минимальны порог для остановки. В этом случае, мне кажется, негативных явлений произойти не должно.

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #75 : 14-01-2011 13:05 » 

Dale, колебания физической системы грузов на пружинах обусловлено, как мне кажется, наличием инертной (не тяжёлой) массы. Её вовсе необязательно тащить в модель.

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

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

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

Добавлено через 16 минут и 59 секунд:
Dale, согласен с вами, но это уже зависит от того, как мы будем обрабатывать положения блоков и натяжения пружин. Если последовательно то действительно велика вероятность что система дестабилизируется и даже могут возникнуть незатухающие колебания. Другое дело если мы будем расчитывать положение каждого блока в определенный момент времени, затем сдвигать все, затем снова проводить оценку и так же введем минимальны порог для остановки. В этом случае, мне кажется, негативных явлений произойти не должно.

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

Но это все умозрительно. Нужно ставить эксперимент, а заодно продумать перспективы перехода от одномерной пружинной модели к двумерной и возможные ловушки. Например: при перемещении блока по горизонтали он попадает в другую вертикальную группу, где другие правила выравнивания. Не потребуется ли при этом изменение структуры блоков/пружин, а если потребуется, какие это будет иметь последствия?
« Последнее редактирование: 14-01-2011 13:22 от Dale » Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #76 : 14-01-2011 13:23 » 

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

Добавлено через 12 минут и 52 секунды:
По поводу наложения горизонтальных слоёв по вертикали. Одномерные выравнивания можно поочерёдно проводить для горизонтали и вертикали. Но вот здесь уже в сходимости я не уверен - это надо думать и проверять.

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

Добавлено через 7 минут и 59 секунд:
overcoder, кстати, для досок с сертификатами, партнёрами и т.д. пружины не подойдут. Дело в том, что для пружин нужно априори иметь некую раскладку, которую остаётся только подровнять. На таких досках априори нет никакой раскладки, есть только множество прямоугольных (или даже многоугольных) блоков, которые нужно компактно разложить на определённой площади - это задача укладки мозаики, и решается она совсем иначе.
« Последнее редактирование: 14-01-2011 13:35 от dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Dale
Блюзмен
Команда клуба

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #77 : 14-01-2011 13:47 » 

Dale, не надо там тщательно параллелить. Ты же сам признал, что штрафы (или напряжения в пружинах) будут с каждым движением уменьшаться - процесс сходится.

Насчет сходимости утверждать не рискну, тут на меня можно не ссылаться. Если взять ряд 1/n, то с увеличением n каждый следующий член уменьшается, но при этом ряд не сходится. Одного уменьшения мало - важна еще скорость убывания. Может, повезет, а может, и нет.
Записан

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

Ходить по воде и разрабатывать программное обеспечение по спецификациям очень просто, когда и то, и другое заморожено. - Edward V. Berard

Любые проблемы в информатике решаются добавлением еще одного уровня косвенности – кроме, разумеется, проблемы переизбытка уровней косвенности. — Дэвид Уилер.
baldr
Команда клуба

cy
Offline Offline
Пол: Мужской
Дорогие россияне


WWW
« Ответ #78 : 31-10-2011 14:27 » 

Подниму топик вверх: на хабре сегодня нашел статью по теме.
http://habrahabr.ru/sandbox/37498/
"JQuery Masonry — динамический layout, верстаем без «дыр»"

Сам плагин: http://masonry.desandro.com/
Записан

Приличный компьютер всегда будет стоить дороже 1000 долларов, потому что 500 долларов - это не вполне прилично
Страниц: 1 2 3 [Все]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines