Алгоритм разметки

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

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

Кто-нибудь знает какие-то такие алгоритмы? или базовый подход к таким проблемам? Оказывается ли это под "вычислительной геометрией"?

Ответ 1

На основе скриншотов и теорий в сообщение в блоге, связанное с Джейсоном Муром в его answer, я бы сказал, что есть десять или более предопределенных размеров блоков, в которые помещается контент. В какой размерной коробке размещен фрагмент контента, он основан на различных параметрах - то, что многие люди перефразируют или любят, могут считаться более приоритетными и, следовательно, получать больший бокс, а предметы с картинками, видеороликами или большим количеством текста также могут быть приоритетными, Эти коробки (предпочтительно с продуманными размерами) затем упаковываются оптимально на страницы (хотя это не простая проблема, и даже Flipbook, похоже, не работает, о чем свидетельствует странное пространство в второй рендеринг потока Facebook из ранее связанного сообщения в блоге).

Из внешнего вида предоставленного фида Facebook Flipbook имеет (по крайней мере) следующие предопределенные размеры ящиков (ширина и высота, заданные в процентах полной ширины/высоты):

Designation | Width | Height | Example                         
---------------------------------------------------------------
full page   | 100%  | 100%   | #12                             
2/3 page    | 100%  | 67%    | #1                              
1/3 note    | 50%   | 33%    | #3, #11                         
1/9 quote   | 50%   | 11%    | #2, #8, #10, #15, #17, #18, #22
1/2 note    | 50%   | 50%    | #16, #19                       
2/3 note    | 50%   | 67%    | ?

Некоторые из них имеют довольно очевидные шаблоны группировки (1/9 кавычек всегда складываются по три за раз, чтобы сформировать блок того же размера, что и 1/3 нота, например), в то время как другие могут быть более свободно упакованы. Аналогичный анализ предоставленного канала Twitter показывает некоторые дополнительные поля.

Резюме

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

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

Акцент здесь должен быть сделан на шаге 1, а также на создании предопределенных ящиков.

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

Ответ 2

Я много разбирался с пониманием компоновки флип-доски. Вот что я придумал https://github.com/reefaq/FlipView

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

Реализованы некоторые функции, такие как

multi flip (иллюзия)
Расположение представлений, если ориентация изменилась как Flipboard
выбор случайного макета

Надеюсь, это поможет вам:)

Ответ 3

Звуки, связанные с алгоритмом ранца. См. Также статью о проблеме упаковки .

Ответ 4

Мне не удалось опубликовать изображения из-за низкой репутации кармы:-), но вот некоторые заметки в виде сообщения в блоге о методе макета.

Ответ 5

Посмотрите на эту библиотеку JavaScript. Кажется интересным

http://masonry.desandro.com

Подход (0,1) - рюкзак.

Ответ 6

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

Жадный алгоритм

Ответ 7

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

Следующая запись в блоге показывает много углубленного анализа, пытаясь расшифровать динамические макеты Flipboard:

Репликация флип-доски Часть III - Как Flipboard выдает контент