3

例として、Google 画像、flickr フォトストリームなどを取り上げます。各画像の寸法とラジオは異なりますが、それらはすべて左側と右側に並んでいます。

私の元のロジックは、javascript でそれらをループして、次の画像が広すぎるポイントにいるときを把握することでした。次に、どのくらいの「余裕」があるかを確認し、全体的に幅を追加しますが、最終的に薄い画像を広くしすぎてしまいます。

これは私がやっていたことのようなものです：

maxwidth = 100;
width = 0;
imgs = [];
foreach image {
    if (width + image.width > maxwidth) {
        space = maxwidth - width / imgs.length;
        foreach imgs {
            img.width = img.width + space;
        }

        imgs = [];
        width = 0;
    }

    imgs.push(image);
    width += image.width;
}
4

1 に答える 1

1

これがパーティションの問題です。フォト ギャラリーへの適用については、Johannes Treitz によるこのブログ投稿で説明されています。推奨される解決策は次のとおりです。

  • 必要な行数kを見つけるには、写真をウィンドウの高さの半分にスケ​​ーリングし、それらの幅を合計し、ウィンドウの幅で割り、丸めます。
  • 写真の縦横比は、一連の重みSとして機能します。既存の線形分割アルゴリズムを使用して、k上のSの最適な分布を見つけます。

ブログ投稿には、ギャラリーを構築するための次の CoffeeScript が含まれています。

viewport_width = $(window).width()
ideal_height = parseInt($(window).height() / 2)
summed_width = photos.reduce ((sum, p) -> sum += p.get('aspect_ratio') * ideal_height), 0
rows = Math.round(summed_width / viewport_width)

if rows < 1
  # (2a) Fallback to just standard size 
  photos.each (photo) -> photo.view.resize parseInt(ideal_height * photo.get('aspect_ratio')), ideal_height
else
  # (2b) Distribute photos over rows using the aspect ratio as weight
  weights = photos.map (p) -> parseInt(p.get('aspect_ratio') * 100)
  partition = linear_partition(weights, rows)

  # (3) Iterate through partition
  index = 0
  row_buffer = new Backbone.Collection
  _.each partition, (row) ->
    row_buffer.reset()
    _.each row, -> row_buffer.add(photos.at(index++))
    summed_ratios = row_buffer.reduce ((sum, p) -> sum += p.get('aspect_ratio')), 0
    row_buffer.each (photo) -> photo.view.resize parseInt(viewport_width / summed_ratios * photo.get('aspect_ratio')), parseInt(viewport_width / summed_ratios)

linear_partition関数は次のように実装されます ( github を参照)。

# Linear partition
# Partitions a sequence of non-negative integers into k ranges
# Based on Óscar López implementation in Python (http://stackoverflow.com/a/7942946)
# Also see http://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK2/NODE45.HTM
# Dependencies: UnderscoreJS (http://www.underscorejs.org)
# Example: linear_partition([9,2,6,3,8,5,8,1,7,3,4], 3) => [[9,2,6,3],[8,5,8],[1,7,3,4]]

linear_partition = (seq, k) =>
  n = seq.length

  return [] if k <= 0
  return seq.map((x) -> [x]) if k > n

  table = (0 for x in [0...k] for y in [0...n])
  solution = (0 for x in [0...k-1] for y in [0...n-1])
  table[i][0] = seq[i] + (if i then table[i-1][0] else 0) for i in [0...n]
  table[0][j] = seq[0] for j in [0...k]
  for i in [1...n]
    for j in [1...k]
      m = _.min(([_.max([table[x][j-1], table[i][0]-table[x][0]]), x] for x in [0...i]), (o) -> o[0])
      table[i][j] = m[0]
      solution[i-1][j-1] = m[1]

  n = n-1
  k = k-2
  ans = []
  while k >= 0
    ans = [seq[i] for i in [(solution[n-1][k]+1)...n+1]].concat ans
    n = solution[n-1][k]
    k = k-1

  [seq[i] for i in [0...n+1]].concat ans
于 2013-10-31T00:35:33.517 に答える